fs/reiser4/pool.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by
   2  * reiser4/README */
   3
   4 /* Fast pool allocation.
   5
   6    There are situations when some sub-system normally asks memory allocator
   7    for only few objects, but under some circumstances could require much
   8    more. Typical and actually motivating example is tree balancing. It needs
   9    to keep track of nodes that were involved into it, and it is well-known
  10    that in reasonable packed balanced tree most (92.938121%) percent of all
  11    balancings end up after working with only few nodes (3.141592 on
  12    average). But in rare cases balancing can involve much more nodes
  13    (3*tree_height+1 in extremal situation).
  14
  15    On the one hand, we don't want to resort to dynamic allocation (slab,
  16     malloc(), etc.) to allocate data structures required to keep track of
  17    nodes during balancing. On the other hand, we cannot statically allocate
  18    required amount of space on the stack, because first: it is useless wastage
  19    of precious resource, and second: this amount is unknown in advance (tree
  20    height can change).
  21
  22    Pools, implemented in this file are solution for this problem:
  23
  24     - some configurable amount of objects is statically preallocated on the
  25     stack
  26
  27     - if this preallocated pool is exhausted and more objects is requested
  28     they are allocated dynamically.
  29
  30    Pools encapsulate distinction between statically and dynamically allocated
  31    objects. Both allocation and recycling look exactly the same.
  32
  33    To keep track of dynamically allocated objects, pool adds its own linkage
  34    to each object.
  35
  36    NOTE-NIKITA This linkage also contains some balancing-specific data. This
  37    is not perfect. On the other hand, balancing is currently the only client
  38    of pool code.
  39
  40    NOTE-NIKITA Another desirable feature is to rewrite all pool manipulation
  41    functions in the style of tslist/tshash, i.e., make them unreadable, but
  42    type-safe.
  43
  44 */
  45
  46 #include "debug.h"
  47 #include "pool.h"
  48 #include "super.h"
  49
  50 #include <linux/types.h>
  51 #include <linux/err.h>
  52
  53 /* initialize new pool object @h */
  54 static void reiser4_init_pool_obj(struct reiser4_pool_header *h)
  55 {
  56         INIT_LIST_HEAD(&h->usage_linkage);
  57         INIT_LIST_HEAD(&h->level_linkage);
  58         INIT_LIST_HEAD(&h->extra_linkage);
  59 }
  60
  61 /* initialize new pool */
  62 void reiser4_init_pool(struct reiser4_pool *pool /* pool to initialize */ ,
  63                        size_t obj_size /* size of objects in @pool */ ,
  64                        int num_of_objs /* number of preallocated objects */ ,
  65                        char *data/* area for preallocated objects */)
  66 {
  67         struct reiser4_pool_header *h;
  68         int i;
  69
  70         assert("nikita-955", pool != NULL);
  71         assert("nikita-1044", obj_size > 0);
  72         assert("nikita-956", num_of_objs >= 0);
  73         assert("nikita-957", data != NULL);
  74
  75         memset(pool, 0, sizeof *pool);
  76         pool->obj_size = obj_size;
  77         pool->data = data;
  78         INIT_LIST_HEAD(&pool->free);
  79         INIT_LIST_HEAD(&pool->used);
  80         INIT_LIST_HEAD(&pool->extra);
  81         memset(data, 0, obj_size * num_of_objs);
  82         for (i = 0; i < num_of_objs; ++i) {
  83                 h = (struct reiser4_pool_header *) (data + i * obj_size);
  84                 reiser4_init_pool_obj(h);
  85                 /* add pool header to the end of pool's free list */
  86                 list_add_tail(&h->usage_linkage, &pool->free);
  87         }
  88 }
  89
  90 /* release pool resources
  91
  92    Release all resources acquired by this pool, specifically, dynamically
  93    allocated objects.
  94
  95 */
  96 void reiser4_done_pool(struct reiser4_pool *pool UNUSED_ARG)
  97 {
  98 }
  99
 100 /* allocate carry object from @pool
 101
 102    First, try to get preallocated object. If this fails, resort to dynamic
 103    allocation.
 104
 105 */
 106 static void *reiser4_pool_alloc(struct reiser4_pool *pool)
 107 {
 108         struct reiser4_pool_header *result;
 109
 110         assert("nikita-959", pool != NULL);
 111
 112         if (!list_empty(&pool->free)) {
 113                 struct list_head *linkage;
 114
 115                 linkage = pool->free.next;
 116                 list_del(linkage);
 117                 INIT_LIST_HEAD(linkage);
 118                 result = list_entry(linkage, struct reiser4_pool_header,
 119                                     usage_linkage);
 120                 BUG_ON(!list_empty(&result->level_linkage) ||
 121                        !list_empty(&result->extra_linkage));
 122         } else {
 123                 /* pool is empty. Extra allocations don't deserve dedicated
 124                    slab to be served from, as they are expected to be rare. */
 125                 result = kmalloc(pool->obj_size, reiser4_ctx_gfp_mask_get());
 126                 if (result != 0) {
 127                         reiser4_init_pool_obj(result);
 128                         list_add(&result->extra_linkage, &pool->extra);
 129                 } else
 130                         return ERR_PTR(RETERR(-ENOMEM));
 131                 BUG_ON(!list_empty(&result->usage_linkage) ||
 132                        !list_empty(&result->level_linkage));
 133         }
 134         ++pool->objs;
 135         list_add(&result->usage_linkage, &pool->used);
 136         memset(result + 1, 0, pool->obj_size - sizeof *result);
 137         return result;
 138 }
 139
 140 /* return object back to the pool */
 141 void reiser4_pool_free(struct reiser4_pool *pool,
 142                        struct reiser4_pool_header *h)
 143 {
 144         assert("nikita-961", h != NULL);
 145         assert("nikita-962", pool != NULL);
 146
 147         --pool->objs;
 148         assert("nikita-963", pool->objs >= 0);
 149
 150         list_del_init(&h->usage_linkage);
 151         list_del_init(&h->level_linkage);
 152
 153         if (list_empty(&h->extra_linkage))
 154                 /*
 155                  * pool header is not an extra one. Push it onto free list
 156                  * using usage_linkage
 157                  */
 158                 list_add(&h->usage_linkage, &pool->free);
 159         else {
 160                 /* remove pool header from pool's extra list and kfree it */
 161                 list_del(&h->extra_linkage);
 162                 kfree(h);
 163         }
 164 }
 165
 166 /* add new object to the carry level list
 167
 168    Carry level is FIFO most of the time, but not always. Complications arise
 169    when make_space() function tries to go to the left neighbor and thus adds
 170    carry node before existing nodes, and also, when updating delimiting keys
 171    after moving data between two nodes, we want left node to be locked before
 172    right node.
 173
 174    Latter case is confusing at the first glance. Problem is that COP_UPDATE
 175    opration that updates delimiting keys is sometimes called with two nodes
 176    (when data are moved between two nodes) and sometimes with only one node
 177    (when leftmost item is deleted in a node). In any case operation is
 178    supplied with at least node whose left delimiting key is to be updated
 179    (that is "right" node).
 180
 181    @pool - from which to allocate new object;
 182    @list - where to add object;
 183    @reference - after (or before) which existing object to add
 184 */
 185 struct reiser4_pool_header *reiser4_add_obj(struct reiser4_pool *pool,
 186                                          struct list_head *list,
 187                                          pool_ordering order,
 188                                          struct reiser4_pool_header *reference)
 189 {
 190         struct reiser4_pool_header *result;
 191
 192         assert("nikita-972", pool != NULL);
 193
 194         result = reiser4_pool_alloc(pool);
 195         if (IS_ERR(result))
 196                 return result;
 197
 198         assert("nikita-973", result != NULL);
 199
 200         switch (order) {
 201         case POOLO_BEFORE:
 202                 __list_add(&result->level_linkage,
 203                            reference->level_linkage.prev,
 204                            &reference->level_linkage);
 205                 break;
 206         case POOLO_AFTER:
 207                 __list_add(&result->level_linkage,
 208                            &reference->level_linkage,
 209                            reference->level_linkage.next);
 210                 break;
 211         case POOLO_LAST:
 212                 list_add_tail(&result->level_linkage, list);
 213                 break;
 214         case POOLO_FIRST:
 215                 list_add(&result->level_linkage, list);
 216                 break;
 217         default:
 218                 wrong_return_value("nikita-927", "order");
 219         }
 220         return result;
 221 }
 222
 223 /* Make Linus happy.
 224    Local variables:
 225    c-indentation-style: "K&R"
 226    mode-name: "LC"
 227    c-basic-offset: 8
 228    tab-width: 8
 229    fill-column: 120
 230    End:
 231 */