yaffs_allocator.c

   1 /*
   2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
   3  *
   4  * Copyright (C) 2002-2011 Aleph One Ltd.
   5  *   for Toby Churchill Ltd and Brightstar Engineering
   6  *
   7  * Created by Charles Manning <charles@aleph1.co.uk>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License version 2 as
  11  * published by the Free Software Foundation.
  12  */
  13
  14 #include "yaffs_allocator.h"
  15 #include "yaffs_guts.h"
  16 #include "yaffs_trace.h"
  17 #include "yportenv.h"
  18
  19 /*
  20  * Each entry in yaffs_tnode_list and yaffs_obj_list hold blocks
  21  * of approx 100 objects that are themn allocated singly.
  22  * This is basically a simplified slab allocator.
  23  *
  24  * We don't use the Linux slab allocator because slab does not allow
  25  * us to dump all the objects in one hit when we do a umount and tear
  26  * down  all the tnodes and objects. slab requires that we first free
  27  * the individual objects.
  28  *
  29  * Once yaffs has been mainlined I shall try to motivate for a change
  30  * to slab to provide the extra features we need here.
  31  */
  32
  33 struct yaffs_tnode_list {
  34         struct yaffs_tnode_list *next;
  35         struct yaffs_tnode *tnodes;
  36 };
  37
  38 struct yaffs_obj_list {
  39         struct yaffs_obj_list *next;
  40         struct yaffs_obj *objects;
  41 };
  42
  43 struct yaffs_allocator {
  44         int n_tnodes_created;
  45         struct yaffs_tnode *free_tnodes;
  46         int n_free_tnodes;
  47         struct yaffs_tnode_list *alloc_tnode_list;
  48
  49         int n_obj_created;
  50         struct list_head free_objs;
  51         int n_free_objects;
  52
  53         struct yaffs_obj_list *allocated_obj_list;
  54 };
  55
  56 static void yaffs_deinit_raw_tnodes(struct yaffs_dev *dev)
  57 {
  58         struct yaffs_allocator *allocator =
  59             (struct yaffs_allocator *)dev->allocator;
  60         struct yaffs_tnode_list *tmp;
  61
  62         if (!allocator) {
  63                 BUG();
  64                 return;
  65         }
  66
  67         while (allocator->alloc_tnode_list) {
  68                 tmp = allocator->alloc_tnode_list->next;
  69
  70                 kfree(allocator->alloc_tnode_list->tnodes);
  71                 kfree(allocator->alloc_tnode_list);
  72                 allocator->alloc_tnode_list = tmp;
  73         }
  74
  75         allocator->free_tnodes = NULL;
  76         allocator->n_free_tnodes = 0;
  77         allocator->n_tnodes_created = 0;
  78 }
  79
  80 static void yaffs_init_raw_tnodes(struct yaffs_dev *dev)
  81 {
  82         struct yaffs_allocator *allocator = dev->allocator;
  83
  84         if (!allocator) {
  85                 BUG();
  86                 return;
  87         }
  88
  89         allocator->alloc_tnode_list = NULL;
  90         allocator->free_tnodes = NULL;
  91         allocator->n_free_tnodes = 0;
  92         allocator->n_tnodes_created = 0;
  93 }
  94
  95 static int yaffs_create_tnodes(struct yaffs_dev *dev, int n_tnodes)
  96 {
  97         struct yaffs_allocator *allocator =
  98             (struct yaffs_allocator *)dev->allocator;
  99         int i;
 100         struct yaffs_tnode *new_tnodes;
 101         u8 *mem;
 102         struct yaffs_tnode *curr;
 103         struct yaffs_tnode *next;
 104         struct yaffs_tnode_list *tnl;
 105
 106         if (!allocator) {
 107                 BUG();
 108                 return YAFFS_FAIL;
 109         }
 110
 111         if (n_tnodes < 1)
 112                 return YAFFS_OK;
 113
 114         /* make these things */
 115         new_tnodes = kmalloc(n_tnodes * dev->tnode_size, GFP_NOFS);
 116         mem = (u8 *) new_tnodes;
 117
 118         if (!new_tnodes) {
 119                 yaffs_trace(YAFFS_TRACE_ERROR,
 120                         "yaffs: Could not allocate Tnodes");
 121                 return YAFFS_FAIL;
 122         }
 123
 124         /* New hookup for wide tnodes */
 125         for (i = 0; i < n_tnodes - 1; i++) {
 126                 curr = (struct yaffs_tnode *)&mem[i * dev->tnode_size];
 127                 next = (struct yaffs_tnode *)&mem[(i + 1) * dev->tnode_size];
 128                 curr->internal[0] = next;
 129         }
 130
 131         curr = (struct yaffs_tnode *)&mem[(n_tnodes - 1) * dev->tnode_size];
 132         curr->internal[0] = allocator->free_tnodes;
 133         allocator->free_tnodes = (struct yaffs_tnode *)mem;
 134
 135         allocator->n_free_tnodes += n_tnodes;
 136         allocator->n_tnodes_created += n_tnodes;
 137
 138         /* Now add this bunch of tnodes to a list for freeing up.
 139          * NB If we can't add this to the management list it isn't fatal
 140          * but it just means we can't free this bunch of tnodes later.
 141          */
 142         tnl = kmalloc(sizeof(struct yaffs_tnode_list), GFP_NOFS);
 143         if (!tnl) {
 144                 yaffs_trace(YAFFS_TRACE_ERROR,
 145                         "Could not add tnodes to management list");
 146                 return YAFFS_FAIL;
 147         } else {
 148                 tnl->tnodes = new_tnodes;
 149                 tnl->next = allocator->alloc_tnode_list;
 150                 allocator->alloc_tnode_list = tnl;
 151         }
 152
 153         yaffs_trace(YAFFS_TRACE_ALLOCATE, "Tnodes added");
 154
 155         return YAFFS_OK;
 156 }
 157
 158 struct yaffs_tnode *yaffs_alloc_raw_tnode(struct yaffs_dev *dev)
 159 {
 160         struct yaffs_allocator *allocator =
 161             (struct yaffs_allocator *)dev->allocator;
 162         struct yaffs_tnode *tn = NULL;
 163
 164         if (!allocator) {
 165                 BUG();
 166                 return NULL;
 167         }
 168
 169         /* If there are none left make more */
 170         if (!allocator->free_tnodes)
 171                 yaffs_create_tnodes(dev, YAFFS_ALLOCATION_NTNODES);
 172
 173         if (allocator->free_tnodes) {
 174                 tn = allocator->free_tnodes;
 175                 allocator->free_tnodes = allocator->free_tnodes->internal[0];
 176                 allocator->n_free_tnodes--;
 177         }
 178
 179         return tn;
 180 }
 181
 182 /* FreeTnode frees up a tnode and puts it back on the free list */
 183 void yaffs_free_raw_tnode(struct yaffs_dev *dev, struct yaffs_tnode *tn)
 184 {
 185         struct yaffs_allocator *allocator = dev->allocator;
 186
 187         if (!allocator) {
 188                 BUG();
 189                 return;
 190         }
 191
 192         if (tn) {
 193                 tn->internal[0] = allocator->free_tnodes;
 194                 allocator->free_tnodes = tn;
 195                 allocator->n_free_tnodes++;
 196         }
 197         dev->checkpoint_blocks_required = 0;    /* force recalculation */
 198 }
 199
 200 /*--------------- yaffs_obj alloaction ------------------------
 201  *
 202  * Free yaffs_objs are stored in a list using obj->siblings.
 203  * The blocks of allocated objects are stored in a linked list.
 204  */
 205
 206 static void yaffs_init_raw_objs(struct yaffs_dev *dev)
 207 {
 208         struct yaffs_allocator *allocator = dev->allocator;
 209
 210         if (!allocator) {
 211                 BUG();
 212                 return;
 213         }
 214
 215         allocator->allocated_obj_list = NULL;
 216         INIT_LIST_HEAD(&allocator->free_objs);
 217         allocator->n_free_objects = 0;
 218 }
 219
 220 static void yaffs_deinit_raw_objs(struct yaffs_dev *dev)
 221 {
 222         struct yaffs_allocator *allocator = dev->allocator;
 223         struct yaffs_obj_list *tmp;
 224
 225         if (!allocator) {
 226                 BUG();
 227                 return;
 228         }
 229
 230         while (allocator->allocated_obj_list) {
 231                 tmp = allocator->allocated_obj_list->next;
 232                 kfree(allocator->allocated_obj_list->objects);
 233                 kfree(allocator->allocated_obj_list);
 234                 allocator->allocated_obj_list = tmp;
 235         }
 236
 237         INIT_LIST_HEAD(&allocator->free_objs);
 238         allocator->n_free_objects = 0;
 239         allocator->n_obj_created = 0;
 240 }
 241
 242 static int yaffs_create_free_objs(struct yaffs_dev *dev, int n_obj)
 243 {
 244         struct yaffs_allocator *allocator = dev->allocator;
 245         int i;
 246         struct yaffs_obj *new_objs;
 247         struct yaffs_obj_list *list;
 248
 249         if (!allocator) {
 250                 BUG();
 251                 return YAFFS_FAIL;
 252         }
 253
 254         if (n_obj < 1)
 255                 return YAFFS_OK;
 256
 257         /* make these things */
 258         new_objs = kmalloc(n_obj * sizeof(struct yaffs_obj), GFP_NOFS);
 259         list = kmalloc(sizeof(struct yaffs_obj_list), GFP_NOFS);
 260
 261         if (!new_objs || !list) {
 262                 kfree(new_objs);
 263                 new_objs = NULL;
 264                 kfree(list);
 265                 list = NULL;
 266                 yaffs_trace(YAFFS_TRACE_ALLOCATE,
 267                         "Could not allocate more objects");
 268                 return YAFFS_FAIL;
 269         }
 270
 271         /* Hook them into the free list */
 272         for (i = 0; i < n_obj; i++)
 273                 list_add(&new_objs[i].siblings, &allocator->free_objs);
 274
 275         allocator->n_free_objects += n_obj;
 276         allocator->n_obj_created += n_obj;
 277
 278         /* Now add this bunch of Objects to a list for freeing up. */
 279
 280         list->objects = new_objs;
 281         list->next = allocator->allocated_obj_list;
 282         allocator->allocated_obj_list = list;
 283
 284         return YAFFS_OK;
 285 }
 286
 287 struct yaffs_obj *yaffs_alloc_raw_obj(struct yaffs_dev *dev)
 288 {
 289         struct yaffs_obj *obj = NULL;
 290         struct list_head *lh;
 291         struct yaffs_allocator *allocator = dev->allocator;
 292
 293         if (!allocator) {
 294                 BUG();
 295                 return obj;
 296         }
 297
 298         /* If there are none left make more */
 299         if (list_empty(&allocator->free_objs))
 300                 yaffs_create_free_objs(dev, YAFFS_ALLOCATION_NOBJECTS);
 301
 302         if (!list_empty(&allocator->free_objs)) {
 303                 lh = allocator->free_objs.next;
 304                 obj = list_entry(lh, struct yaffs_obj, siblings);
 305                 list_del_init(lh);
 306                 allocator->n_free_objects--;
 307         }
 308
 309         return obj;
 310 }
 311
 312 void yaffs_free_raw_obj(struct yaffs_dev *dev, struct yaffs_obj *obj)
 313 {
 314
 315         struct yaffs_allocator *allocator = dev->allocator;
 316
 317         if (!allocator) {
 318                 BUG();
 319                 return;
 320         }
 321
 322         /* Link into the free list. */
 323         list_add(&obj->siblings, &allocator->free_objs);
 324         allocator->n_free_objects++;
 325 }
 326
 327 void yaffs_deinit_raw_tnodes_and_objs(struct yaffs_dev *dev)
 328 {
 329
 330         if (!dev->allocator) {
 331                 BUG();
 332                 return;
 333         }
 334
 335         yaffs_deinit_raw_tnodes(dev);
 336         yaffs_deinit_raw_objs(dev);
 337         kfree(dev->allocator);
 338         dev->allocator = NULL;
 339 }
 340
 341 void yaffs_init_raw_tnodes_and_objs(struct yaffs_dev *dev)
 342 {
 343         struct yaffs_allocator *allocator;
 344
 345         if (dev->allocator) {
 346                 BUG();
 347                 return;
 348         }
 349
 350         allocator = kmalloc(sizeof(struct yaffs_allocator), GFP_NOFS);
 351         if (allocator) {
 352                 dev->allocator = allocator;
 353                 yaffs_init_raw_tnodes(dev);
 354                 yaffs_init_raw_objs(dev);
 355         }
 356 }
 357