2 * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
4 * Copyright (C) 2002-2011 Aleph One Ltd.
5 * for Toby Churchill Ltd and Brightstar Engineering
7 * Created by Charles Manning <charles@aleph1.co.uk>
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.
14 #include "yaffs_allocator.h"
15 #include "yaffs_guts.h"
16 #include "yaffs_trace.h"
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.
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.
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.
33 struct yaffs_tnode_list
{
34 struct yaffs_tnode_list
*next
;
35 struct yaffs_tnode
*tnodes
;
38 struct yaffs_obj_list
{
39 struct yaffs_obj_list
*next
;
40 struct yaffs_obj
*objects
;
43 struct yaffs_allocator
{
45 struct yaffs_tnode
*free_tnodes
;
47 struct yaffs_tnode_list
*alloc_tnode_list
;
50 struct list_head free_objs
;
53 struct yaffs_obj_list
*allocated_obj_list
;
56 static void yaffs_deinit_raw_tnodes(struct yaffs_dev
*dev
)
58 struct yaffs_allocator
*allocator
=
59 (struct yaffs_allocator
*)dev
->allocator
;
60 struct yaffs_tnode_list
*tmp
;
67 while (allocator
->alloc_tnode_list
) {
68 tmp
= allocator
->alloc_tnode_list
->next
;
70 kfree(allocator
->alloc_tnode_list
->tnodes
);
71 kfree(allocator
->alloc_tnode_list
);
72 allocator
->alloc_tnode_list
= tmp
;
75 allocator
->free_tnodes
= NULL
;
76 allocator
->n_free_tnodes
= 0;
77 allocator
->n_tnodes_created
= 0;
80 static void yaffs_init_raw_tnodes(struct yaffs_dev
*dev
)
82 struct yaffs_allocator
*allocator
= dev
->allocator
;
89 allocator
->alloc_tnode_list
= NULL
;
90 allocator
->free_tnodes
= NULL
;
91 allocator
->n_free_tnodes
= 0;
92 allocator
->n_tnodes_created
= 0;
95 static int yaffs_create_tnodes(struct yaffs_dev
*dev
, int n_tnodes
)
97 struct yaffs_allocator
*allocator
=
98 (struct yaffs_allocator
*)dev
->allocator
;
100 struct yaffs_tnode
*new_tnodes
;
102 struct yaffs_tnode
*curr
;
103 struct yaffs_tnode
*next
;
104 struct yaffs_tnode_list
*tnl
;
114 /* make these things */
115 new_tnodes
= kmalloc(n_tnodes
* dev
->tnode_size
, GFP_NOFS
);
116 mem
= (u8
*) new_tnodes
;
119 yaffs_trace(YAFFS_TRACE_ERROR
,
120 "yaffs: Could not allocate Tnodes");
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
;
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
;
135 allocator
->n_free_tnodes
+= n_tnodes
;
136 allocator
->n_tnodes_created
+= n_tnodes
;
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.
142 tnl
= kmalloc(sizeof(struct yaffs_tnode_list
), GFP_NOFS
);
144 yaffs_trace(YAFFS_TRACE_ERROR
,
145 "Could not add tnodes to management list");
148 tnl
->tnodes
= new_tnodes
;
149 tnl
->next
= allocator
->alloc_tnode_list
;
150 allocator
->alloc_tnode_list
= tnl
;
153 yaffs_trace(YAFFS_TRACE_ALLOCATE
, "Tnodes added");
158 struct yaffs_tnode
*yaffs_alloc_raw_tnode(struct yaffs_dev
*dev
)
160 struct yaffs_allocator
*allocator
=
161 (struct yaffs_allocator
*)dev
->allocator
;
162 struct yaffs_tnode
*tn
= NULL
;
169 /* If there are none left make more */
170 if (!allocator
->free_tnodes
)
171 yaffs_create_tnodes(dev
, YAFFS_ALLOCATION_NTNODES
);
173 if (allocator
->free_tnodes
) {
174 tn
= allocator
->free_tnodes
;
175 allocator
->free_tnodes
= allocator
->free_tnodes
->internal
[0];
176 allocator
->n_free_tnodes
--;
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
)
185 struct yaffs_allocator
*allocator
= dev
->allocator
;
193 tn
->internal
[0] = allocator
->free_tnodes
;
194 allocator
->free_tnodes
= tn
;
195 allocator
->n_free_tnodes
++;
197 dev
->checkpoint_blocks_required
= 0; /* force recalculation */
200 /*--------------- yaffs_obj alloaction ------------------------
202 * Free yaffs_objs are stored in a list using obj->siblings.
203 * The blocks of allocated objects are stored in a linked list.
206 static void yaffs_init_raw_objs(struct yaffs_dev
*dev
)
208 struct yaffs_allocator
*allocator
= dev
->allocator
;
215 allocator
->allocated_obj_list
= NULL
;
216 INIT_LIST_HEAD(&allocator
->free_objs
);
217 allocator
->n_free_objects
= 0;
220 static void yaffs_deinit_raw_objs(struct yaffs_dev
*dev
)
222 struct yaffs_allocator
*allocator
= dev
->allocator
;
223 struct yaffs_obj_list
*tmp
;
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
;
237 INIT_LIST_HEAD(&allocator
->free_objs
);
238 allocator
->n_free_objects
= 0;
239 allocator
->n_obj_created
= 0;
242 static int yaffs_create_free_objs(struct yaffs_dev
*dev
, int n_obj
)
244 struct yaffs_allocator
*allocator
= dev
->allocator
;
246 struct yaffs_obj
*new_objs
;
247 struct yaffs_obj_list
*list
;
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
);
261 if (!new_objs
|| !list
) {
266 yaffs_trace(YAFFS_TRACE_ALLOCATE
,
267 "Could not allocate more objects");
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
);
275 allocator
->n_free_objects
+= n_obj
;
276 allocator
->n_obj_created
+= n_obj
;
278 /* Now add this bunch of Objects to a list for freeing up. */
280 list
->objects
= new_objs
;
281 list
->next
= allocator
->allocated_obj_list
;
282 allocator
->allocated_obj_list
= list
;
287 struct yaffs_obj
*yaffs_alloc_raw_obj(struct yaffs_dev
*dev
)
289 struct yaffs_obj
*obj
= NULL
;
290 struct list_head
*lh
;
291 struct yaffs_allocator
*allocator
= dev
->allocator
;
298 /* If there are none left make more */
299 if (list_empty(&allocator
->free_objs
))
300 yaffs_create_free_objs(dev
, YAFFS_ALLOCATION_NOBJECTS
);
302 if (!list_empty(&allocator
->free_objs
)) {
303 lh
= allocator
->free_objs
.next
;
304 obj
= list_entry(lh
, struct yaffs_obj
, siblings
);
306 allocator
->n_free_objects
--;
312 void yaffs_free_raw_obj(struct yaffs_dev
*dev
, struct yaffs_obj
*obj
)
315 struct yaffs_allocator
*allocator
= dev
->allocator
;
322 /* Link into the free list. */
323 list_add(&obj
->siblings
, &allocator
->free_objs
);
324 allocator
->n_free_objects
++;
327 void yaffs_deinit_raw_tnodes_and_objs(struct yaffs_dev
*dev
)
330 if (!dev
->allocator
) {
335 yaffs_deinit_raw_tnodes(dev
);
336 yaffs_deinit_raw_objs(dev
);
337 kfree(dev
->allocator
);
338 dev
->allocator
= NULL
;
341 void yaffs_init_raw_tnodes_and_objs(struct yaffs_dev
*dev
)
343 struct yaffs_allocator
*allocator
;
345 if (dev
->allocator
) {
350 allocator
= kmalloc(sizeof(struct yaffs_allocator
), GFP_NOFS
);
352 dev
->allocator
= allocator
;
353 yaffs_init_raw_tnodes(dev
);
354 yaffs_init_raw_objs(dev
);