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