yaffs_allocator.c

   1 /*
   2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
   3  *
   4  * Copyright (C) 2002-2010 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 #ifdef CONFIG_YAFFS_KMALLOC_ALLOCATOR
  20 /* This is an alternative debug allocator. Don't use for production code. */
  21
  22 void yaffs_deinit_raw_tnodes_and_objs(struct yaffs_dev *dev)
  23 {
  24         dev = dev;
  25 }
  26
  27 void yaffs_init_raw_tnodes_and_objs(struct yaffs_dev *dev)
  28 {
  29         dev = dev;
  30 }
  31
  32 struct yaffs_tnode *yaffs_alloc_raw_tnode(struct yaffs_dev *dev)
  33 {
  34         return kmalloc(dev->tnode_size, GFP_NOFS);
  35 }
  36
  37 void yaffs_free_raw_tnode(struct yaffs_dev *dev, struct yaffs_tnode *tn)
  38 {
  39         dev = dev;
  40         kfree(tn);
  41 }
  42
  43 void yaffs_init_raw_objs(struct yaffs_dev *dev)
  44 {
  45         dev = dev;
  46 }
  47
  48 void yaffs_deinit_raw_objs(struct yaffs_dev *dev)
  49 {
  50         dev = dev;
  51 }
  52
  53 struct yaffs_obj *yaffs_alloc_raw_obj(struct yaffs_dev *dev)
  54 {
  55         dev = dev;
  56         return kmalloc(sizeof(struct yaffs_obj));
  57 }
  58
  59 void yaffs_free_raw_obj(struct yaffs_dev *dev, struct yaffs_obj *obj)
  60 {
  61
  62         dev = dev;
  63         kfree(obj);
  64 }
  65
  66 #else
  67
  68 struct yaffs_tnode_list {
  69         struct yaffs_tnode_list *next;
  70         struct yaffs_tnode *tnodes;
  71 };
  72
  73 struct yaffs_obj_list {
  74         struct yaffs_obj_list *next;
  75         struct yaffs_obj *objects;
  76 };
  77
  78 struct yaffs_allocator {
  79         int n_tnodes_created;
  80         struct yaffs_tnode *free_tnodes;
  81         int n_free_tnodes;
  82         struct yaffs_tnode_list *alloc_tnode_list;
  83
  84         int n_obj_created;
  85         struct yaffs_obj *free_objs;
  86         int n_free_objects;
  87
  88         struct yaffs_obj_list *allocated_obj_list;
  89 };
  90
  91 static void yaffs_deinit_raw_tnodes(struct yaffs_dev *dev)
  92 {
  93         struct yaffs_allocator *allocator =
  94             (struct yaffs_allocator *)dev->allocator;
  95         struct yaffs_tnode_list *tmp;
  96
  97         if (!allocator) {
  98                 YBUG();
  99                 return;
 100         }
 101
 102         while (allocator->alloc_tnode_list) {
 103                 tmp = allocator->alloc_tnode_list->next;
 104
 105                 kfree(allocator->alloc_tnode_list->tnodes);
 106                 kfree(allocator->alloc_tnode_list);
 107                 allocator->alloc_tnode_list = tmp;
 108         }
 109
 110         allocator->free_tnodes = NULL;
 111         allocator->n_free_tnodes = 0;
 112         allocator->n_tnodes_created = 0;
 113 }
 114
 115 static void yaffs_init_raw_tnodes(struct yaffs_dev *dev)
 116 {
 117         struct yaffs_allocator *allocator = dev->allocator;
 118
 119         if (allocator) {
 120                 allocator->alloc_tnode_list = NULL;
 121                 allocator->free_tnodes = NULL;
 122                 allocator->n_free_tnodes = 0;
 123                 allocator->n_tnodes_created = 0;
 124         } else {
 125                 YBUG();
 126         }
 127 }
 128
 129 static int yaffs_create_tnodes(struct yaffs_dev *dev, int n_tnodes)
 130 {
 131         struct yaffs_allocator *allocator =
 132             (struct yaffs_allocator *)dev->allocator;
 133         int i;
 134         struct yaffs_tnode *new_tnodes;
 135         u8 *mem;
 136         struct yaffs_tnode *curr;
 137         struct yaffs_tnode *next;
 138         struct yaffs_tnode_list *tnl;
 139
 140         if (!allocator) {
 141                 YBUG();
 142                 return YAFFS_FAIL;
 143         }
 144
 145         if (n_tnodes < 1)
 146                 return YAFFS_OK;
 147
 148         /* make these things */
 149         new_tnodes = kmalloc(n_tnodes * dev->tnode_size, GFP_NOFS);
 150         mem = (u8 *) new_tnodes;
 151
 152         if (!new_tnodes) {
 153                 yaffs_trace(YAFFS_TRACE_ERROR,
 154                         "yaffs: Could not allocate Tnodes");
 155                 return YAFFS_FAIL;
 156         }
 157
 158         /* New hookup for wide tnodes */
 159         for (i = 0; i < n_tnodes - 1; i++) {
 160                 curr = (struct yaffs_tnode *)&mem[i * dev->tnode_size];
 161                 next = (struct yaffs_tnode *)&mem[(i + 1) * dev->tnode_size];
 162                 curr->internal[0] = next;
 163         }
 164
 165         curr = (struct yaffs_tnode *)&mem[(n_tnodes - 1) * dev->tnode_size];
 166         curr->internal[0] = allocator->free_tnodes;
 167         allocator->free_tnodes = (struct yaffs_tnode *)mem;
 168
 169         allocator->n_free_tnodes += n_tnodes;
 170         allocator->n_tnodes_created += n_tnodes;
 171
 172         /* Now add this bunch of tnodes to a list for freeing up.
 173          * NB If we can't add this to the management list it isn't fatal
 174          * but it just means we can't free this bunch of tnodes later.
 175          */
 176         tnl = kmalloc(sizeof(struct yaffs_tnode_list), GFP_NOFS);
 177         if (!tnl) {
 178                 yaffs_trace(YAFFS_TRACE_ERROR,
 179                         "Could not add tnodes to management list");
 180                 return YAFFS_FAIL;
 181         } else {
 182                 tnl->tnodes = new_tnodes;
 183                 tnl->next = allocator->alloc_tnode_list;
 184                 allocator->alloc_tnode_list = tnl;
 185         }
 186
 187         yaffs_trace(YAFFS_TRACE_ALLOCATE, "Tnodes added");
 188
 189         return YAFFS_OK;
 190 }
 191
 192 struct yaffs_tnode *yaffs_alloc_raw_tnode(struct yaffs_dev *dev)
 193 {
 194         struct yaffs_allocator *allocator =
 195             (struct yaffs_allocator *)dev->allocator;
 196         struct yaffs_tnode *tn = NULL;
 197
 198         if (!allocator) {
 199                 YBUG();
 200                 return NULL;
 201         }
 202
 203         /* If there are none left make more */
 204         if (!allocator->free_tnodes)
 205                 yaffs_create_tnodes(dev, YAFFS_ALLOCATION_NTNODES);
 206
 207         if (allocator->free_tnodes) {
 208                 tn = allocator->free_tnodes;
 209                 allocator->free_tnodes = allocator->free_tnodes->internal[0];
 210                 allocator->n_free_tnodes--;
 211         }
 212
 213         return tn;
 214 }
 215
 216 /* FreeTnode frees up a tnode and puts it back on the free list */
 217 void yaffs_free_raw_tnode(struct yaffs_dev *dev, struct yaffs_tnode *tn)
 218 {
 219         struct yaffs_allocator *allocator = dev->allocator;
 220
 221         if (!allocator) {
 222                 YBUG();
 223                 return;
 224         }
 225
 226         if (tn) {
 227                 tn->internal[0] = allocator->free_tnodes;
 228                 allocator->free_tnodes = tn;
 229                 allocator->n_free_tnodes++;
 230         }
 231         dev->checkpoint_blocks_required = 0;    /* force recalculation */
 232 }
 233
 234 static void yaffs_init_raw_objs(struct yaffs_dev *dev)
 235 {
 236         struct yaffs_allocator *allocator = dev->allocator;
 237
 238         if (allocator) {
 239                 allocator->allocated_obj_list = NULL;
 240                 allocator->free_objs = NULL;
 241                 allocator->n_free_objects = 0;
 242         } else {
 243                 YBUG();
 244         }
 245 }
 246
 247 static void yaffs_deinit_raw_objs(struct yaffs_dev *dev)
 248 {
 249         struct yaffs_allocator *allocator = dev->allocator;
 250         struct yaffs_obj_list *tmp;
 251
 252         if (!allocator) {
 253                 YBUG();
 254                 return;
 255         }
 256
 257         while (allocator->allocated_obj_list) {
 258                 tmp = allocator->allocated_obj_list->next;
 259                 kfree(allocator->allocated_obj_list->objects);
 260                 kfree(allocator->allocated_obj_list);
 261
 262                 allocator->allocated_obj_list = tmp;
 263         }
 264
 265         allocator->free_objs = NULL;
 266         allocator->n_free_objects = 0;
 267         allocator->n_obj_created = 0;
 268 }
 269
 270 static int yaffs_create_free_objs(struct yaffs_dev *dev, int n_obj)
 271 {
 272         struct yaffs_allocator *allocator = dev->allocator;
 273         int i;
 274         struct yaffs_obj *new_objs;
 275         struct yaffs_obj_list *list;
 276
 277         if (!allocator) {
 278                 YBUG();
 279                 return YAFFS_FAIL;
 280         }
 281
 282         if (n_obj < 1)
 283                 return YAFFS_OK;
 284
 285         /* make these things */
 286         new_objs = kmalloc(n_obj * sizeof(struct yaffs_obj), GFP_NOFS);
 287         list = kmalloc(sizeof(struct yaffs_obj_list), GFP_NOFS);
 288
 289         if (!new_objs || !list) {
 290                 kfree(new_objs);
 291                 new_objs = NULL;
 292                 kfree(list);
 293                 list = NULL;
 294                 yaffs_trace(YAFFS_TRACE_ALLOCATE,
 295                         "Could not allocate more objects");
 296                 return YAFFS_FAIL;
 297         }
 298
 299         /* Hook them into the free list */
 300         for (i = 0; i < n_obj - 1; i++) {
 301                 new_objs[i].siblings.next =
 302                     (struct list_head *)(&new_objs[i + 1]);
 303         }
 304
 305         new_objs[n_obj - 1].siblings.next = (void *)allocator->free_objs;
 306         allocator->free_objs = new_objs;
 307         allocator->n_free_objects += n_obj;
 308         allocator->n_obj_created += n_obj;
 309
 310         /* Now add this bunch of Objects to a list for freeing up. */
 311
 312         list->objects = new_objs;
 313         list->next = allocator->allocated_obj_list;
 314         allocator->allocated_obj_list = list;
 315
 316         return YAFFS_OK;
 317 }
 318
 319 struct yaffs_obj *yaffs_alloc_raw_obj(struct yaffs_dev *dev)
 320 {
 321         struct yaffs_obj *obj = NULL;
 322         struct yaffs_allocator *allocator = dev->allocator;
 323
 324         if (!allocator) {
 325                 YBUG();
 326                 return obj;
 327         }
 328
 329         /* If there are none left make more */
 330         if (!allocator->free_objs)
 331                 yaffs_create_free_objs(dev, YAFFS_ALLOCATION_NOBJECTS);
 332
 333         if (allocator->free_objs) {
 334                 obj = allocator->free_objs;
 335                 allocator->free_objs =
 336                     (struct yaffs_obj *)(allocator->free_objs->siblings.next);
 337                 allocator->n_free_objects--;
 338         }
 339
 340         return obj;
 341 }
 342
 343 void yaffs_free_raw_obj(struct yaffs_dev *dev, struct yaffs_obj *obj)
 344 {
 345
 346         struct yaffs_allocator *allocator = dev->allocator;
 347
 348         if (!allocator)
 349                 YBUG();
 350         else {
 351                 /* Link into the free list. */
 352                 obj->siblings.next = (struct list_head *)(allocator->free_objs);
 353                 allocator->free_objs = obj;
 354                 allocator->n_free_objects++;
 355         }
 356 }
 357
 358 void yaffs_deinit_raw_tnodes_and_objs(struct yaffs_dev *dev)
 359 {
 360         if (dev->allocator) {
 361                 yaffs_deinit_raw_tnodes(dev);
 362                 yaffs_deinit_raw_objs(dev);
 363
 364                 kfree(dev->allocator);
 365                 dev->allocator = NULL;
 366         } else {
 367                 YBUG();
 368         }
 369 }
 370
 371 void yaffs_init_raw_tnodes_and_objs(struct yaffs_dev *dev)
 372 {
 373         struct yaffs_allocator *allocator;
 374
 375         if (!dev->allocator) {
 376                 allocator = kmalloc(sizeof(struct yaffs_allocator), GFP_NOFS);
 377                 if (allocator) {
 378                         dev->allocator = allocator;
 379                         yaffs_init_raw_tnodes(dev);
 380                         yaffs_init_raw_objs(dev);
 381                 }
 382         } else {
 383                 YBUG();
 384         }
 385 }
 386
 387 #endif