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
33struct yaffs_tnode_list {
34	struct yaffs_tnode_list *next;
35	struct yaffs_tnode *tnodes;
36};
37
38struct yaffs_obj_list {
39	struct yaffs_obj_list *next;
40	struct yaffs_obj *objects;
41};
42
43struct 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
56static 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
80static 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
95static 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
158struct 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 */
183void 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
206static 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
220static 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
242static 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
287struct 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
312void 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
327void 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
341void 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}
357
358