# Doug Lea's malloc implementation

This module packages Doug Lea's `malloc` implementation and extends it in various optional ways developed at Opera. Its API documentation may be generated by running the command `doxygen` in the `documentation/` sub-directory. Its primary API comprises the C standard library memory management functions plus, for C++, the operators `new`, `new []`, `delete []` and `delete`. It has a secondary API to manage its initialization and shut-down; and, when compiled in single-block mode, to interrogate the status of its single block of memory.

Since this module provides, at least in some of its configurations, the memory allocation infrastructure relied upon by all other Opera code, including during initialization and termination, it must be initialized first and shut down last. Consequently it does not participate in core-2's global Opera object process, but is rather part of the OpMemoryState infrastructure provided by the memory module. The interval between the OpMemoryState object's initialization and shut-down is this module's life-time; normally, its primary API is not available except during this life-time, although these rules may be bent if you know what you're doing (see below). Please refer to the OpMemoryState documentation for more information on the initialization and deinitialization of the memory infrastructure.

On some operating systems (e.g. Linux), the underlying system calls by which this module obtains memory from the operating system may over commit the machine's memory. In such a case, there is normally no way for this module to abide by ANSI C's specified behaviour for memory allocation when insufficient memory is available; a call to `malloc()` may return a non-`NULL` pointer to memory which, when actually accessed, turns out to not be available. This makes OOM-handling impossible. However, if we only call the underlying system once, during start-up, to lay claim to all the memory we are ever going to need, this module can manage that monolithic block of memory without running into problems with over-commit. Subsequently this module can correctly report OOM, when it happens, and Opera can reclaim memory suitably. Consequently, projects with a strong need for correct OOM-handling should use single-block mode (see `API_DLM_SINGLE_BLOCK` below).

## Configuration

The module is configured via the feature, tweak and API systems in core-2 but by direct use of its own defines in core-1. Relevant settings (and the defines they activate when `YES`):

Features:
  FEATURE_3P_LEA_MALLOC (HAVE_DL_MALLOC)
    If this is YES, this module's implementation of `malloc` is compiled and used by Opera. Otherwise, all of the following is irrelevant.
  FEATURE_LEA_MALLOC_PREFIX (USE_DL_PREFIX)
    If `YES`, prefix the primary API function names with `dl` so that this memory allocation infrastructure may be used alongside the system one; otherwise, this implementation supersedes the system one.
  FEATURE_LEA_MALLOC_CONSTRAINED (CONSTRAIN_OPERA_MEMORY_USAGE)
    If `YES`, use the Opera allocator for the whole process and constrain memory usage by selectively allowing for allocations to fail on OOM depending on where they originate from. The memory usage is constrained by setting limits on the heap size and/or the total amount of memory allocated from the constrained allocation sites.
Tweaks (see `module.tweaks` for the gory details):
  TWEAK_LEA_MALLOC_LOCK (USE_MALLOC_LOCK)

    Thread-safety support: protects each call to any primary API function with calls to `OpMemory::MallocLock()`/`OpMemory::MallocUnlock()` functions (as declared in `pi/system/OpMemory.h`). This TWEAK will be replaced by the equivalent from the memory module: `TWEAK_MEMORY_USE_LOCKING` (`MEMORY_USE_LOCKING`).

  TWEAK_LEA_MALLOC_PLATFORM_CONFIG (LEA_MALLOC_CONFIG_HEADER)

    The underlying `malloc` implementation provided by Doug Lea has some further defines with which interested parties might wish to experiment. Put settings for these internal defines for the module in a header within your platform, then tweak `LEA_MALLOC_CONFIG_HEADER` to be a string naming that file relative to the Opera root directory (or some other directory in your compiler's include path); the module shall use a `#include` of that file to obtain its config. This tweak's default, `"modules/lea_malloc/dummy_config.h"`, contains documentation for what you may want to set in your platform configuration. (If this file contains configuration for your platform, you should move it out to your own configuration header.)

  TWEAK_LEA_MALLOC_REENTRANT (MALLOC_BLOCK_SIGNALS)

    Experimental re-entrancy prevention. Needed if any signal handler (in use by any part of the application, including shared libraries) is liable to call the primary API functions; otherwise, if such a signal is caught during a call to a primary API function, the resulting re-entrant call may find preconditions it takes for granted being violated. That can lead to very nasty and confusing consequences. Signal-handlers should not generally call this module's primary API functions.

APIs (see module.export):
  API_DLM_CHECK (LEA_MALLOC_EXTERN_CHECK)

    Provides a minimal API for asking this module to check sanity of its internal state.

  API_DLM_CONSTRAIN (LEA_MALLOC_API_CONSTRAIN)

    Support for limits on the amount of memory we use, adaptable so that only selected parts of our own code are in danger of suffering OOM, provided fake memory management functions are used to check for potential OOM before calling other code (e.g. shared libraries) which shall perform real allocations.

  API_DLM_FULL_MEMAPI (LEA_MALLOC_FULL_MEMAPI)

    Include all functions of the standard memory API, not just the ones used directly by Opera. This is needed if `FEATURE_LEA_MALLOC_PREFIX` is off and the binary loads shared libraries - either via shared linkage or as plugins - which might conceivably call functions in this full API.

  API_DLM_SINGLE_BLOCK (LEA_MALLOC_MONOBLOCK)

    Provides the SingleBlockHeap class (see `lea_monoblock`).

In builds which rely on dynamically linked (a.k.a. shared) libraries, the initialization hooks of such libraries are called before `main` and, consequently, outside this module's life-time. It is possible that such hook functions may call memory allocation functions (c.f. bug #174325). There are three ways to prevent that being disastrous, when using this module:

- turn on `FEATURE_LEA_MALLOC_PREFIX` (define `USE_DL_PREFIX`) and map `op_malloc` and friends to (optionally: wrapper functions which call) the suitably-prefixed versions of this module's primary API functions; libraries will then use the system's equivalents of this module's API, so you must take care to prevent any mix-up between memory managed by this module and by the system;
- ensure that Opera is entirely single-threaded (so you must use synchronous DNS) and use static memory and initialization for this module's state data; this isn't an option if you use any library which spawns its own threads (at least, not if those threads are apt to call this module's primary API);
- turn on `TWEAK_MEMORY_USE_LOCKING` (`MEMORY_USE_LOCKING`) (or `TWEAK_LEA_MALLOC_LOCK` (`USE_MALLOC_LOCK`) if the former is not available) to prevent the threading from causing grief, and implement your own `OpMemory::MallocLock()`/`OpMemory::MallocUnlock()` functions (as declared in `pi/system/OpMemory.h`). Your provided locking functions must properly handle being called from outside `main()`. Here are two ways of achieving this:
  - Statically initialize the lock, so that the locking functions may be readily used outside `main()`.
  - If you can ensure that no simultaneous calls to the primary API will happen outside of `main()`, you may forego locking until the lock is initialized, and simply have the locking functions return immediate success before the lock is initialized.

Note that the second of these is incompatible with Core's policy on globals (the third might also be, depending on how you choose to implement your lock).

## Footprint

There are numerous functions that can be removed from this package to reduce code size, if only slightly: `valloc`, `pvalloc`, `independent_calloc`, `independent_comalloc`, and possibly some of the tuning functions.

However, we have no way to know which libraries we might load at runtime that might try to exercise these functions. If we don't provide all of them, and a library exercises one we missed, it'll get the system libraries, which can lead to very mysterious crashers ! However, when using `FEATURE_LEA_MALLOC_PREFIX`, this should not be an issue.

## Statement on memory usage and management

- This module allocates almost no memory for itself, but rather allocates memory from the system on behalf of other modules. Thus, it functions as a layer of code between Opera's memory management infrastructure (i.e. op_malloc(), op_free, and friends), and the platform's memory management infrastructure.
- The OOM policy is very simple; if an allocation fails, `NULL` is returned, and must be handled appropriately by the caller.
- These is no usage or handling of exceptions (e.g. `TRAP/LEAVE`) in this module.
- The module is extremely tunable in how it requests and releases memory from the underlying platform. Please read the documentation on the various TWEAKs and APIs offered by the module for more information.
- The selftests provided by this module, features a comprehensive verification of the module's functionality. However, stress-testing (either in number of allocations, or in size of allocations) is not done by the selftests in order to work on as many platforms as possible.
- The long-term goal of the module is to stay as close as possible (both in behaviour and implementation) to the upstream dlmalloc source. This includes minimizing the number of Opera-specific hacks done within the module, and separating any necesarry hacks as much as possible from the original code in `malloc.c`.

## Implementation overview

As stated above, the main part of this module is a repackaging of Doug Lea's `malloc` implementation. His code is found largely unchanged in `malloc.c` and `malloc.h`. Any other code found in this module provides Opera-specific extensions or workarounds, but in the end, everything centers around Doug Lea's `malloc`.

For an overview of how Doug Lea's `malloc` works, please refer to this article. Also, `malloc.c` is heavily commented with documentation on how the code works.

Here follows an overview of the Opera-specific extensions and workarounds provided elsewhere in this module:

Secondary API for initialization/shutdown/metainformation

  Found in `lea_malloc.h` and `lea_malloc.cpp`. Provides the secondary memory API: Code responsible for initialization, shutdown and (in single-block mode; see below) interrogating the block and free memory space.

Single-block allocation manager

  Found in `lea_monoblock.h` and `lea_monoblock.cpp`. Provides the `SingleBlockHeap` class for making a dlmalloc allocator managing a single contiguous block of memory. See `API_DLM_SINGLE_BLOCK` for more details.

Other extensions and workarounds

  Most of these are found in `malloc_extra.cpp`. These include implementations of C++'s operator `new` and `delete`, and code related to `FEATURE_LEA_MALLOC_CONSTRAINED`.