yaffs_allocator.c

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