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