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