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