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