From 338e010b45d7bd411e2bbcedcd8ef195be40c2be Mon Sep 17 00:00:00 2001
From: Tim Peters <tim.peters@gmail.com>
Date: Mon, 1 Apr 2002 19:23:44 +0000
Subject: [PATCH] Restructured my pool-management overview in terms of the
 three possible pool states.  I think it's much clearer now.

Added a new long overdue block-management overview comment block.

I believe the comments are in good shape now.

Added two comments about possible small optimizations (one getting rid
of runtime multiplications at the cost of a new pool_header member; the
other getting rid of runtime divisions and the pool_header capacity
member, at the cost of a static const vector of 32 uints).
---
 Objects/obmalloc.c | 82 ++++++++++++++++++++++++++++++++++------------
 1 file changed, 61 insertions(+), 21 deletions(-)

diff --git a/Objects/obmalloc.c b/Objects/obmalloc.c
index 303084422f..94e23d7a83 100644
--- a/Objects/obmalloc.c
+++ b/Objects/obmalloc.c
@@ -268,27 +268,66 @@ all partially used pools holding small blocks with "size class idx" i. So
 usedpools[0] corresponds to blocks of size 8, usedpools[2] to blocks of size
 16, and so on:  index 2*i <-> blocks of size (i+1)<<ALIGNMENT_SHIFT.
 
-The partially used pools for a given index are linked together via their
-pool_header's prevpool and nextpool members.  "Partially used" means at least
-one block in the pool is currently allocated, *and* at least one block in the
-pool is not currently allocated.
-
-When all blocks in a pool are allocated, the pool is unlinked from the list,
-and isn't linked to from anything anymore (you can't find it then from
-anything obmalloc.c knows about); the pool's own prevpool and nextpool
-pointers are set to point to itself.  The comments say the pool "is full" then.
-
-When a small block is returned to pymalloc, there are two cases.  If its pool
-was full, its pool is relinked into the appropriate usedpools[] list, at the
-front (so the next allocation of the same size class will be taken from this
-pool).  Else its pool was not full, the pool is already in a usedpools[]
-list, and isn't moved.  Instead the block is just linked to the front of the
-pool's own freeblock singly-linked list.  However, if that makes the pool
-entirely free of allocated blocks (the comments say the pool "is empty" then),
-the pool is unlinked from usedpools[], and inserted at the front of the
-(file static) singly-linked freepools list, via the pool header's nextpool
-member; prevpool is meaningless in this case.  Pools put on the freepools
-list can be changed to belong to a different size class.
+Pools are carved off the current arena highwater mark (file static arenabase)
+as needed.  Once carved off, a pool is in one of three states forever after:
+
+used == partially used, neither empty nor full
+    At least one block in the pool is currently allocated, and at least one
+    block in the pool is not currently allocated (note this implies a pool
+    has room for at least two blocks).
+    This is a pool's initial state, as a pool is created only when malloc
+    needs space.
+    The pool holds blocks of a fixed size, and is in the circular list headed
+    at usedpools[i] (see above).  It's linked to the other used pools of the
+    same size class via the pool_header's nextpool and prevpool members.
+    If all but one block is currently allocated, a malloc can cause a
+    transition to the full state.  If all but one block is not currently
+    allocated, a free can cause a transition to the empty state.
+
+full == all the pool's blocks are currently allocated
+    On transition to full, a pool is unlinked from its usedpools[] list.
+    It's not linked to from anything then anymore, and its nextpool and
+    prevpool members are meaningless until it transitions back to used.
+    A free of a block in a full pool puts the pool back in the used state.
+    Then it's linked in at the front of the appropriate usedpools[] list, so
+    that the next allocation for its size class will reuse the freed block.
+
+empty == all the pool's blocks are currently available for allocation
+    On transition to empty, a pool is unlinked from its usedpools[] list,
+    and linked to the front of the (file static) singly-linked freepools list,
+    via its nextpool member.  The prevpool member has no meaning in this case.
+    Empty pools have no inherent size class:  the next time a malloc finds
+    an empty list in usedpools[], it takes the first pool off of freepools.
+    If the size class needed happens to be the same as the size class the pool
+    last had, some expensive initialization can be skipped (including an
+    integer division -- XXX since the value
+
+	pool->capacity = (POOL_SIZE - POOL_OVERHEAD) / size;
+
+    is invariant across all pools of a given size class, it may make more
+    sense to compute those at compile-time into a const vector indexed by
+    size class, and lose the pool->capacity member and the runtime divisions).
+
+
+Block Management
+
+Blocks within pools are again carved out as needed.  pool->freeblock points to
+the start of a singly-linked list of free blocks within the pool.  When a
+block is freed, it's inserted at the front of its pool's freeblock list.  Note
+that the available blocks in a pool are *not* linked all together when a pool
+is initialized.  Instead only "the first" (lowest address) block is set up,
+setting pool->freeblock to NULL.  This is consistent with that pymalloc
+strives at all levels (arena, pool, and block) never to touch a piece of
+memory until it's actually needed.  So long as a pool is in the used state,
+we're certain there *is* a block available for allocating.  If pool->freeblock
+is NULL then, that means we simply haven't yet gotten to one of the higher-
+address blocks.  The address of "the next" available block can be computed
+then from pool->ref.count (the number of currently allocated blocks).  This
+computation can be expensive, because it requires an integer multiply.
+However, so long as the pool's size class doesn't change, it's a one-time cost
+for that block; the computation could be made cheaper via adding a highwater
+pointer to the pool_header, but the tradeoff is murky.
+
 
 Major obscurity:  While the usedpools vector is declared to have poolp
 entries, it doesn't really.  It really contains two pointers per (conceptual)
@@ -510,6 +549,7 @@ error:
  */
 #define ADDRESS_IN_RANGE(P, I) \
 	((I) < narenas && (uptr)(P) - arenas[I] < (uptr)ARENA_SIZE)
+
 /*==========================================================================*/
 
 /* malloc */
-- 
2.50.1