src/util/afs_atomlist.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 #include <afsconfig.h>
  11 #include <afs/param.h>
  12
  13
  14 #ifdef KERNEL
  15 #include "afs_atomlist.h"
  16 #else /* KERNEL */
  17 #include "afs_atomlist.h"
  18 #endif /* KERNEL */
  19
  20 /*
  21  * The afs_atomlist abstract data type is for efficiently allocating
  22  * space for small structures.
  23  *
  24  * The atoms in an afs_atomlist are allocated in blocks.  The blocks
  25  * are chained together so that they can be freed when the afs_atomlist
  26  * is destroyed.  When a new block is allocated, its atoms are chained
  27  * together and added to the free list of atoms.
  28  *
  29  * If the requested atom size is smaller than the size of a pointer,
  30  * afs_atomlist_create() silently increases the atom size.  If
  31  * the atom size would result in incorrectly aligned pointers,
  32  * afs_atomlist_create() silently increases the atom size as necessary.
  33  *
  34  * A block of atoms is organized as follows.
  35  *
  36  * ---------------------------------------------------------------
  37  * | atom | atom | atom | ... | atom | nextblock | wasted space* |
  38  * ---------------------------------------------------------------
  39  * \____ atoms_per_block atoms ______/
  40  *
  41  * (*) A block may or may not contain wasted space at the end.  The
  42  * amount of wasted space depends on the size of a block, the size of an
  43  * atom, and the size of the pointer to the next block.  For instance,
  44  * if a block is 4096 bytes, an atom is 12 bytes, and a pointer is 4
  45  * bytes, there is no wasted space in a block.
  46  *
  47  * The pointer to the next block is stored AFTER all the atoms in the
  48  * block.  Here's why.
  49  *
  50  * If we put the pointer to the next block before the atoms,
  51  * followed immediately by the atoms, we would be assuming that the
  52  * atoms could be aligned on a pointer boundary.
  53  *
  54  * If we tried to solve the alignment problem by allocating an entire
  55  * atom for the pointer to the next block, we might waste space
  56  * gratuitously.  Say a block is 4096 bytes, an atom is 24 bytes, and a
  57  * pointer is 8 bytes.  In this case a block can hold 170 atoms, with 16
  58  * bytes left over.  This isn't enough space for another atom, but it is
  59  * enough space for the pointer to the next block.  There is no need to
  60  * use one of the atoms to store the pointer to the next block.
  61  *
  62  * So, we store the pointer to the next block after the end of the atoms
  63  * in the block.  In the worst case, the block size is an exact multiple
  64  * of the atom size, and we waste an entire atom to store the pointer to
  65  * the next block.  But we hope it is more typical that there is enough
  66  * extra space after the atoms to store the pointer to the next block.
  67  *
  68  * A more sophisticated scheme would keep the pointers to the atom
  69  * blocks in a separate list of blocks.  It would eliminate the
  70  * fragmentation of the atom blocks in the case where the block size
  71  * is a multiple of the atom size.  However, it is more complicated to
  72  * understand and to implement, so I chose not to do it at this time.
  73  * If fragmentation turns out to be a serious enough issue, we can
  74  * change the afs_atomlist implementation without affecting its users.
  75  */
  76
  77 struct afs_atomlist {
  78     size_t atom_size;
  79     size_t block_size;
  80     size_t atoms_per_block;
  81     void *(*allocate) (size_t n);
  82     void (*deallocate) (void *p, size_t n);
  83     void *atom_head;            /* pointer to head of atom free list */
  84     void *block_head;           /* pointer to block list */
  85 };
  86
  87 afs_atomlist *
  88 afs_atomlist_create(size_t atom_size, size_t block_size,
  89                     void *(*allocate) (size_t n)
  90                     , void (*deallocate) (void *p, size_t n)
  91     )
  92 {
  93     afs_atomlist *al;
  94     size_t atoms_per_block;
  95     size_t extra_space;
  96
  97     /*
  98      * Atoms must be at least as big as a pointer in order for
  99      * our implementation of the atom free list to work.
 100      */
 101     if (atom_size < sizeof(void *)) {
 102         atom_size = sizeof(void *);
 103     }
 104
 105     /*
 106      * Atoms must be a multiple of the size of a pointer
 107      * so that the pointers in the atom free list will be
 108      * properly aligned.
 109      */
 110     if (atom_size % sizeof(void *) != (size_t) 0) {
 111         size_t pad = sizeof(void *) - (atom_size % sizeof(void *));
 112         atom_size += pad;
 113     }
 114
 115     /*
 116      * Blocks are the unit of memory allocation.
 117      *
 118      * 1) Atoms are allocated out of blocks.
 119      *
 120      * 2) sizeof(void *) bytes in each block, aligned on a sizeof(void *)
 121      * boundary, are used to chain together the blocks so that they can
 122      * be freed later.  This reduces the space in each block for atoms.
 123      * It is intended that atoms should be small relative to the size of
 124      * a block, so this should not be a problem.
 125      *
 126      * At a minimum, a block must be big enough for one atom and
 127      * a pointer to the next block.
 128      */
 129     if (block_size < atom_size + sizeof(void *))
 130         return 0;
 131
 132     atoms_per_block = block_size / atom_size;
 133     extra_space = block_size - (atoms_per_block * atom_size);
 134     if (extra_space < sizeof(void *)) {
 135         if (atoms_per_block < (size_t) 2) {
 136             return 0;           /* INTERNAL ERROR! */
 137         }
 138         atoms_per_block--;
 139     }
 140
 141     al = allocate(sizeof *al);
 142     if (!al)
 143         return 0;
 144
 145     al->atom_size = atom_size;
 146     al->block_size = block_size;
 147     al->allocate = allocate;
 148     al->deallocate = deallocate;
 149     al->atom_head = 0;
 150     al->block_head = 0;
 151     al->atoms_per_block = atoms_per_block;
 152
 153     return al;
 154 }
 155
 156 void
 157 afs_atomlist_destroy(afs_atomlist * al)
 158 {
 159     void *cur;
 160     void *next;
 161
 162     for (cur = al->block_head; cur; cur = next) {
 163         next = *(void **)((char *)cur + al->atoms_per_block * al->atom_size);
 164         al->deallocate(cur, al->block_size);
 165     }
 166     al->deallocate(al, sizeof *al);
 167 }
 168
 169 void *
 170 afs_atomlist_get(afs_atomlist * al)
 171 {
 172     void *data;
 173
 174     /* allocate a new block if necessary */
 175     if (!al->atom_head) {
 176         void *block;
 177         void *p;
 178         size_t i;
 179
 180         block = al->allocate(al->block_size);
 181         if (!block) {
 182             return 0;
 183         }
 184
 185         /* add this block to the chain of allocated blocks */
 186         *(void **)((char *)block + al->atoms_per_block * al->atom_size) =
 187             al->block_head;
 188         al->block_head = block;
 189
 190         /* add this block's atoms to the atom free list */
 191         p = block;
 192         for (i = 0; i + 1 < al->atoms_per_block; i++) {
 193             *(void **)p = (char *)p + al->atom_size;
 194             p = (char *)p + al->atom_size;
 195         }
 196         *(void **)p = 0;
 197         al->atom_head = block;
 198     }
 199
 200     if (!al->atom_head) {
 201         return 0;               /* INTERNAL ERROR */
 202     }
 203
 204     data = al->atom_head;
 205     al->atom_head = *(void **)data;
 206
 207     return data;
 208 }
 209
 210 void
 211 afs_atomlist_put(afs_atomlist * al, void *data)
 212 {
 213     *(void **)data = al->atom_head;
 214     al->atom_head = data;
 215 }