unified/doc: Update memory pools section of Kernel Primer

Also tweaks the memory maps section so that the two sections
are laid out in a similar manner.

Change-Id: I3abd69dd7e6c65cd1d6a4f12b3b14aa1b166ca5b
Signed-off-by: Allan Stephens <allan.stephens@windriver.com>

2 files changed, 140 insertions, 102 deletions

diff --git a/doc/kernel_v2/memory/maps.rst b/doc/kernel_v2/memory/maps.rst
index 0d6b96a9e..27d53671c 100644
--- a/doc/kernel_v2/memory/maps.rst
+++ b/doc/kernel_v2/memory/maps.rst
@@ -3,8 +3,11 @@
 Memory Maps
 ###########
 
-A :dfn:`memory map` is a kernel object that allows fixed-size memory blocks
+A :dfn:`memory map` is a kernel object that allows memory blocks
 to be dynamically allocated from a designated memory region.
+All memory blocks in a memory map have a single fixed size,
+allowing them to be allocated and released efficiently
+and avoiding memory fragmentation concerns.
 
 .. contents::
     :local:
@@ -18,15 +21,14 @@ by its memory address.
 
 A memory map has the following key properties:
 
-* A **buffer** that provides the memory for the memory map's blocks.
-
 * The **block size** of each block, measured in bytes.
+  It must be at least 4 bytes long.
 
 * The **number of blocks** available for allocation.
+  It must be greater than zero.
 
-The number of blocks and block size values must be greater than zero.
-The block size must be at least 4 bytes, to allow the kernel
-to maintain a linked list of unallocated blocks.
+* A **buffer** that provides the memory for the memory map's blocks.
+  It must be at least "block size" times "number of blocks" bytes long.
 
 A thread that needs to use a memory block simply allocates it from a memory
 map. When the thread finishes with a memory block,
@@ -38,14 +40,19 @@ Any number of thread may wait on an empty memory map simultaneously;
 when a memory block becomes available, it is given to the highest-priority
 thread that has waited the longest.
 
-The kernel manages memory blocks in an efficient and deterministic
-manner that eliminates the risk of memory fragmentation problems which can
-arise when using variable-size blocks.
-
 Unlike a heap, more than one memory map can be defined, if needed. This
 allows for a memory map with smaller blocks and others with larger-sized
 blocks. Alternatively, a memory pool object may be used.
 
+Internal Operation
+==================
+
+A memory map's buffer is an array of fixed-size blocks,
+with no wasted space between the blocks.
+
+The memory map keeps track of unallocated blocks using a linked list;
+the first 4 bytes of each unused block provide the necessary linkage.
+
 Implementation
 **************
 
@@ -81,15 +88,16 @@ Allocating a Memory Block
 A memory block is allocated by calling :cpp:func:`k_mem_map_alloc()`.
 
 The following code builds on the example above, and waits up to 100 milliseconds
-for a memory block to become available,
-and gives a warning if it is not obtained in that time.
+for a memory block to become available, then fills it with zeroes.
+A warning is printed if a suitable block is not obtained.
 
 .. code-block:: c
 
     char *block_ptr;
 
     if (k_mem_map_alloc(&my_map, &block_ptr, 100) == 0)) {
-        /* utilize memory block */
+        memset(block_ptr, 0, 400);
+	...
     } else {
         printf("Memory allocation time-out");
     }
@@ -116,7 +124,7 @@ Suggested Uses
 Use a memory map to allocate and free memory in fixed-size blocks.
 
 Use memory map blocks when sending large amounts of data from one thread
-to another.
+to another, to avoid unnecessary copying of the data.
 
 Configuration Options
 *********************
diff --git a/doc/kernel_v2/memory/pools.rst b/doc/kernel_v2/memory/pools.rst
index 6169006dd..494aa3d9c 100644
--- a/doc/kernel_v2/memory/pools.rst
+++ b/doc/kernel_v2/memory/pools.rst
@@ -1,10 +1,18 @@
 .. _memory_pools_v2:
 
-Memory Pools [TBD]
-##################
+Memory Pools
+############
 
-A :dfn:`memory pool` is a kernel object that allows variable-size memory blocks
+A :dfn:`memory pool` is a kernel object that allows memory blocks
 to be dynamically allocated from a designated memory region.
+Unlike :ref:`memory map <microkernel_memory_maps>` objects,
+the memory blocks in a memory pool can be of any size,
+thereby reducing the amount of wasted memory when an application
+needs to allocate storage for data structures of different sizes.
+The memory pool uses a "buddy memory allocation" algorithm
+to efficiently partition larger blocks into smaller ones,
+allowing blocks of different sizes to be allocated and released efficiently
+while limiting memory fragmentation concerns.
 
 .. contents::
     :local:
@@ -13,25 +21,28 @@ to be dynamically allocated from a designated memory region.
 Concepts
 ********
 
-Unlike :ref:`memory map <microkernel_memory_maps>` objects, which support
-memory blocks of only a *single* size, a memory pool can support memory blocks
-of *various* sizes. The memory pool does this by subdividing blocks into smaller
-chunks, where possible, to more closely match the actual needs of a requesting
-task.
-
 Any number of memory pools can be defined. Each memory pool is referenced
 by its memory address.
 
 A memory pool has the following key properties:
 
-* A **minimum** and **maximum** block size, measured in bytes.
-* The **number of maximum-size memory blocks** initially available.
+* A **minimum block size**, measured in bytes.
+  This must be at least 4 bytes long.
+
+* A **maximum block size**, measured in bytes.
+  This should be a power of 4 times larger than the minimum block size.
+  That is, "maximum block size" must equal "minimum block size" times 4^n,
+  where n is greater than or equal to zero.
 
-The number of blocks and block size values must be greater than zero.
-The block size must be defined as a multiple of the word size.
+* The **number of maximum-size blocks** initially available.
+  This must be greater than zero.
+
+* A **buffer** that provides the memory for the memory pool's blocks.
+  This must be at least "maximum block size" times
+  "number of maximum-size blocks" bytes long.
 
 A thread that needs to use a memory block simply allocates it from a memory
-pool. Following a successful allocation, the :c:data:`pointer_to_data` field
+pool. Following a successful allocation, the :c:data:`data` field
 of the block descriptor supplied by the thread indicates the starting address
 of the memory block. When the thread is finished with a memory block,
 it must release the block back to the memory pool so the block can be reused.
@@ -40,124 +51,134 @@ If a block of the desired size is unavailable, a thread can optionally wait
 for one to become available.
 Any number of threads may wait on a memory pool simultaneously;
 when a suitable memory block becomes available, it is given to
-the highest-priority task that has waited the longest.
-
-When a request for memory is sufficiently smaller than an available
-memory pool block, the memory pool will automatically split the block into
-4 smaller blocks. The resulting smaller blocks can also be split repeatedly,
-until a block just larger than the needed size is available, or the minimum
-block size, as specified in the MDEF, is reached.
-
-If the memory pool cannot find an available block that is at least
-the requested size, it will attempt to create one by merging adjacent
-free blocks. If a suitable block can't be created, the request fails.
-
-Although a memory pool uses efficient algorithms to manage its blocks,
-the splitting of available blocks and merging of free blocks takes time
-and increases overhead block allocation. The larger the allowable
-number of splits, the larger the overhead. However, the minimum and maximum
-block-size parameters specified for a pool can be used to control the amount
-of splitting, and thus the amount of overhead.
+the highest-priority thread that has waited the longest.
 
 Unlike a heap, more than one memory pool can be defined, if needed. For
 example, different applications can utilize different memory pools; this
 can help prevent one application from hijacking resources to allocate all
 of the available blocks.
 
+Internal Operation
+==================
+
+A memory pool's buffer is an array of maximum-size blocks,
+with no wasted space between the blocks.
+Each of these "level 0" blocks is a *quad-block* that can be
+partitioned into four smaller "level 1" blocks of equal size, if needed.
+Likewise, each level 1 block is itself a quad-block that can be partitioned
+into four smaller "level 2" blocks in a similar way, and so on.
+Thus, memory pool blocks can be recursively partitioned into quarters
+until blocks of the minimum size are obtained,
+at which point no further partitioning can occur.
+
+A memory pool keeps track of how its buffer space has been partitioned
+using an array of *block set* data structures. There is one block set
+for each partitioning level supported by the pool, or (to put it another way)
+for each block size. A block set keeps track of all free blocks of its
+associated size using an array of *quad-block status* data structures.
+
+When an application issues a request for a memory block,
+the memory pool first determines the size of the smallest block
+that will satisfy the request, and examines the corresponding block set.
+If the block set contains a free block, the block is marked as used
+and the allocation process is complete.
+If the block set does not contain a free block,
+the memory pool attempts to create one automatically by splitting a free block
+of a larger size or by merging free blocks of smaller sizes;
+if a suitable block can't be created, the allocation request fails.
+
+.. note::
+    By default, memory pools will attempt to split a larger block
+    before trying to merge smaller blocks. However, they can also
+    be configured to merge smaller blocks first, or to skip
+    the merging step entirely. In the latter case, merging of smaller
+    blocks only occurs when the application explicitly issues
+    a request to defragment the entire memory pool.
+
+The memory pool's block merging and splitting process is done efficiently,
+but it is a recursive algorithm that may incur significant overhead.
+In addition, the merging algorithm cannot combine adjacent free blocks
+of different sizes, nor can it merge adjacent free blocks of the same size
+if they belong to different parent quad-blocks. As a consequence,
+memory fragmentation issues can still be encountered when using a memory pool.
+
+When an application releases a previously allocated memory block
+it is simply marked as a free block in its associated block set.
+The memory pool does not attempt to merge the newly freed block,
+allowing it to be easily reallocated in its existing form.
+
 Implementation
 **************
 
 Defining a Memory Pool
 ======================
 
-The following parameters must be defined:
-
-   *name*
-          This specifies a unique name for the memory pool.
-
-   *min_block_size*
-          This specifies the minimum memory block size in bytes.
-          It should be a multiple of the processor's word size.
-
-   *max_block_size*
-          This specifies the maximum memory block size in bytes.
-          It should be a power of 4 times larger than *minBlockSize*;
-          therefore, maxBlockSize = minBlockSize * 4^n, where n>=0.
-
-   *num_max*
-          This specifies the number of maximum size memory blocks
-          available at startup.
+A memory pool is defined using a variable of type :c:type:`struct k_mem_pool`.
+However, since a memory pool also requires a number of variable-size data
+structures to represent its block sets and the status of its quad-blocks,
+the kernel does not support the run-time definition of a memory pool.
+A memory pool can only be defined and initialized at compile time
+by calling :c:macro:`K_MEM_POOL_DEFINE()`.
 
-Public Memory Pool
-------------------
+The following code defines and initializes a memory pool that has 3 blocks
+of 4096 bytes each, which can be partitioned into blocks as small as 64 bytes.
+(That is, the memory pool supports block sizes of 4096, 1024, 256,
+and 64 bytes.)
+Observe that the macro defines all of the memory pool data structures,
+as well as its buffer.
 
-Define the memory pool in the application's MDEF with the following
-syntax:
-
-.. code-block:: console
-
-   POOL name min_block_size max_block_size num_max
-
-For example, the file :file:`projName.mdef` defines two memory pools
-as follows:
-
-.. code-block:: console
-
-    % POOL NAME            MIN  MAX     NMAX
-    % =======================================
-      POOL MY_POOL         32   8192      1
-      POOL SECOND_POOL_ID  64   1024      5
+.. code-block:: c
 
-A public memory pool can be referenced by name from any source file that
-includes the file :file:`zephyr.h`.
-
-.. note::
-   Private memory pools are not supported by the Zephyr kernel.
+    K_MEM_POOL_DEFINE(my_map, 64, 4096, 3);
 
 Allocating a Memory Block
 =========================
 
 A memory block is allocated by calling :cpp:func:`k_mem_pool_alloc()`.
 
-The following code waits up to 100 milliseconds for a 256 byte memory block
-to become available, then fills it with zeroes. A warning is issued
-if a suitable block is not obtained.
+The following code builds on the example above, and waits up to 100 milliseconds
+for a 200 byte memory block to become available, then fills it with zeroes.
+A warning is issued if a suitable block is not obtained.
+
+Note that the application will actually receive a 256 byte memory block,
+since that is the closest matching size supported by the memory pool.
 
 .. code-block:: c
 
     struct k_mem_block block;
 
-    if (k_mem_pool_alloc(&my_pool, 256, &block, 100) == 0)) {
-        memset(block.pointer_to_data, 0, 256);
+    if (k_mem_pool_alloc(&my_pool, &block, 200, 100) == 0)) {
+        memset(block.data, 0, 200);
 	...
     } else {
         printf("Memory allocation time-out");
     }
 
-Freeing a Memory Block
-======================
+Releasing a Memory Block
+========================
 
 A memory block is released by calling :cpp:func:`k_mem_pool_free()`.
 
-The following code allocates a memory block, then releases it once
-it is no longer needed.
+The following code builds on the example above, and allocates a 75 byte
+memory block, then releases it once it is no longer needed. (A 256 byte
+memory block is actually used to satisfy the request.)
 
 .. code-block:: c
 
     struct k_mem_block block;
 
-    k_mem_pool_alloc(&my_pool, size, &block, K_FOREVER);
-     /* use memory block */
+    k_mem_pool_alloc(&my_pool, &block, 75, K_FOREVER);
+    ... /* use memory block */
     k_mem_pool_free(&block);
 
 Manually Defragmenting a Memory Pool
 ====================================
 
-This code instructs the memory pool to concatenate any unused memory blocks
-that can be merged. Doing a full defragmentation of the entire memory pool
-before allocating a number of memory blocks may be more efficient than doing
-an implicit partial defragmentation of the memory pool each time a memory
-block allocation occurs.
+This code instructs the memory pool to concatenate unused memory blocks
+into their parent quad-blocks wherever possible. Doing a full defragmentation
+of the entire memory pool before allocating a number of memory blocks
+may be more efficient than relying on the partial defragmentation that can
+occur automatically each time a memory block allocation is requested.
 
 .. code-block:: c
 
@@ -171,6 +192,15 @@ Use a memory pool to allocate memory in variable-size blocks.
 Use memory pool blocks when sending large amounts of data from one thread
 to another, to avoid unnecessary copying of the data.
 
+Configuration Options
+*********************
+
+Related configuration options:
+
+* CONFIG_MEM_POOL_AD_BEFORE_SEARCH_FOR_BIGGER_BLOCK
+* CONFIG_MEM_POOL_AD_AFTER_SEARCH_FOR_BIGGER_BLOCK
+* CONFIG_MEM_POOL_AD_NONE
+
 APIs
 ****