FreeCalypso > hg > freecalypso-sw

comparison gsm-fw/services/ffs/reclaim.c @ 213:ef7d7da61c56

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
FFS code integration: remaining C files imported, but not yet integrated
author Michael Spacefalcon <msokolov@ivan.Harhan.ORG>
date Mon, 06 Jan 2014 04:20:29 +0000
parents
children 0eb85790c0ed
comparison
equal deleted inserted replaced
212:3ebe6409e8bc 213:ef7d7da61c56
1 /******************************************************************************
2 * Flash File System (ffs)
3 * Idea, design and coding by Mads Meisner-Jensen, mmj@ti.com
4 *
5 * FFS core reclaim functionality
6 *
7 * $Id: reclaim.c 1.4.1.28 Thu, 08 Jan 2004 15:05:23 +0100 tsj $
8 *
9 ******************************************************************************/
10
11 #ifndef TARGET
12 #include "ffs.cfg"
13 #endif
14
15 #include "ffs/ffs.h"
16 #include "ffs/board/core.h"
17 #include "ffs/board/drv.h"
18 #include "ffs/board/ffstrace.h"
19
20 #include <stdlib.h> // rand()
21
22 /******************************************************************************
23 * Inodes Reclaim
24 ******************************************************************************/
25
26 void inodes_recurse(iref_t i)
27 {
28 iref_t pi;
29 struct inode_s *ip, *newip;
30
31 tw(tr(TR_BEGIN, TrReclaimLow, "inodes_recurse(%d) {\n", i));
32
33 ip = inode_addr(i);
34 newip = (struct inode_s *) offset2addr(dev.binfo[fs.newinodes].offset) + i;
35
36 // copy inode dir to new block, except child, sibling and copied
37 ffsdrv.write((uint32*) &newip->location, (uint32*) &ip->location, sizeof(location_t));
38 ffsdrv.write_halfword((uint16*) &newip->size, ip->size);
39 ffsdrv_write_byte (&newip->flags, ip->flags);
40 ffsdrv.write_halfword((uint16*) &newip->sequence, ip->sequence);
41 ffsdrv.write_halfword((uint16*) &newip->updates, ip->updates);
42 bstat[fs.newinodes].used++;
43
44 // if no children of this dir, we have no more work to do
45 if (ip->child == (iref_t) IREF_NULL) {
46 tw(tr(TR_END, TrReclaimLow, "}\n"));
47 return;
48 }
49
50 pi = -i;
51 i = ip->child;
52 ip = inode_addr(i);
53
54 do {
55 tw(tr(TR_FUNC, TrReclaimLow, "pi = %d, i = %d", pi, i));
56
57 tw(tr(TR_NULL, TrReclaimLow, ", size = %d, location = 0x%x", ip->size,
58 ip->location));
59
60 tw(tr(TR_NULL, TrReclaimLow, ", name_addr = 0x%x",
61 addr2name(offset2addr(location2offset(ip->location)))));
62
63 if (is_object(ip, OT_SEGMENT))
64 tw(tr(TR_NULL, TrReclaimLow, ", (segment)\n"));
65
66 else
67 tw(tr(TR_NULL, TrReclaimLow, ", '%s'\n",
68 (ip->size ? addr2name(offset2addr(location2offset(ip->location)))
69 : "(cleaned)")));
70
71 if (is_object_valid(ip))
72 {
73 if (is_object(ip, OT_DIR)) {
74 tw(tr(TR_NULL, TrReclaimLow, "recursing...\n", i));
75 inodes_recurse(i);
76 }
77 else {
78 tw(tr(TR_NULL, TrReclaimLow, "copying...\n"));
79 // copy inode to new block, except child, sibling and copied
80 newip = (struct inode_s *)
81 offset2addr(dev.binfo[fs.newinodes].offset) + i;
82 ffsdrv.write((uint32*) &newip->location, (uint32*) &ip->location, sizeof(location_t));
83 ffsdrv.write_halfword((uint16*) &newip->size, ip->size);
84 ffsdrv_write_byte (&newip->flags, ip->flags);
85 ffsdrv.write_halfword((uint16*) &newip->sequence, ip->sequence);
86 ffsdrv.write_halfword((uint16*) &newip->updates, ip->updates);
87 bstat[fs.newinodes].used++;
88 }
89
90 tw(tr(TR_FUNC, TrReclaimLow, "Linking: %d->%d\n",pi, i));
91 // now write the child or sibling link of previous inode
92 newip = (struct inode_s *)
93 offset2addr(dev.binfo[fs.newinodes].offset);
94 if (pi > 0)
95 ffsdrv.write_halfword((uint16*) &(newip + pi)->sibling, i);
96 else
97 ffsdrv.write_halfword((uint16*) &(newip + (-pi))->child, i);
98
99 pi = i; // save index of previous inode
100
101 if (ip->child != (iref_t) IREF_NULL && is_object(ip, OT_FILE)) {
102 iref_t pis, is;
103 struct inode_s *ips;
104 pis = i;
105 ips = ip;
106
107 tw(tr(TR_FUNC, TrReclaimLow, "Follow segment head\n"));
108 // While child is valid
109 while ((is = ips->child) != (iref_t) IREF_NULL) {
110
111 // Get child
112 is = ips->child;
113 ips = inode_addr(is);
114 tw(tr(TR_FUNC, TrReclaimLow, "Child ok, got new child i = %d\n", is));
115 // While object not is valid
116 while (!is_object_valid(ips)) {
117 tw(tr(TR_FUNC, TrReclaimLow, "pi = %d, i = %d c(cleaned)\n", pis, is));
118 // If sibling are valid
119 if (ips->sibling != (iref_t) IREF_NULL) {
120 // Get sibling
121 is = ips->sibling;
122 ips = inode_addr(is);
123 tw(tr(TR_FUNC, TrReclaimLow, "Sibling ok, got new sibling i = %d\n", is));
124 }
125 else {
126 tw(tr(TR_FUNC, TrReclaimLow, "Sibling = FF (%d)\n", ips->sibling));
127 break; // Nothing more todo, child and sibling = FF
128 }
129 }
130 // If object is valid
131 if (is_object_valid(ips)) {
132 tw(tr(TR_NULL, TrReclaimLow, "copying...\n"));
133 // copy inode to new block, except child, sibling and copied
134 newip = (struct inode_s *)
135 offset2addr(dev.binfo[fs.newinodes].offset) + is;
136 ffsdrv.write((uint32*) &newip->location, (uint32*) &ips->location, sizeof(location_t));
137 ffsdrv.write_halfword((uint16*) &newip->size, ips->size);
138 ffsdrv_write_byte (&newip->flags, ips->flags);
139 ffsdrv.write_halfword((uint16*) &newip->sequence, ips->sequence);
140 ffsdrv.write_halfword((uint16*) &newip->updates, ips->updates);
141 bstat[fs.newinodes].used++;
142
143 tw(tr(TR_FUNC, TrReclaimLow, "Linking child: %d->%d\n",pis, is));
144 // now write the child link of previous inode
145 newip = (struct inode_s *)
146 offset2addr(dev.binfo[fs.newinodes].offset);
147 ffsdrv.write_halfword((uint16*) &(newip + (pis))->child, is);
148
149 pis = is; // save index of previous inode
150
151 }
152 else {
153 tw(tr(TR_FUNC, TrReclaimLow, "Sibling = FF (%d, %d)\n",
154 ips->sibling, ips->child));
155 }
156
157 }
158 }
159 }
160 else {
161 tw(tr(TR_NULL, TrReclaimLow, "(ignoring)\n"));
162 }
163 i = ip->sibling;
164 ip = inode_addr(i);
165
166 } while (i != (iref_t) IREF_NULL);
167
168 tw(tr(TR_END, TrReclaimLow, "}\n"));
169 }
170
171 // Reclaim inodes, eg. move inodes to another block and erase old one.
172 effs_t inodes_reclaim(void)
173 {
174 tw(tr(TR_BEGIN, TrIReclaim, "inodes_reclaim() {\n"));
175 ttw(str(TTrRec, "irec{"));
176
177 if (fs.initerror != EFFS_OK) {
178 tw(tr(TR_END, TrIReclaim, "} %d\n", fs.initerror));
179 ttw(ttr(TTrRec, "} %d" NL, fs.initerror));
180 return fs.initerror;
181 }
182
183 if ((fs.newinodes = block_alloc(1, BF_COPYING)) < 0) {
184 tw(tr(TR_END, TrIReclaim, "} %d\n", EFFS_NOBLOCKS));
185 ttw(ttr(TTrRec, "} %d" NL, EFFS_NOBLOCKS));
186 return EFFS_NOBLOCKS;
187 }
188
189 statistics_update_irec(bstat[fs.inodes].used - bstat[fs.inodes].lost,
190 bstat[fs.inodes].lost);
191
192 // copy all inodes...
193 bstat[fs.newinodes].used = 0;
194 inodes_recurse(fs.root);
195
196 block_commit();
197
198 tw(tr(TR_END, TrIReclaim, "} 0\n"));
199 ttw(str(TTrRec, "} 0" NL));
200
201 return EFFS_OK;
202 }
203
204 #if (FFS_TEST == 0)
205 #define BLOCK_COMMIT_TEST(testcase, text)
206 #else
207 #if (TARGET == 0)
208 // NOTEME: We have compressed the macro code because it will NOT compile on
209 // Unix otherwise. So until we find out why, we use this as a work-around.
210 #define BLOCK_COMMIT_TEST(testcase, text) if (fs.testflags == testcase) { tw(tr(TR_FUNC, TrData, "} (" text ")\n")); return; }
211 #else
212 #define BLOCK_COMMIT_TEST(testcase, text) if (fs.testflags == testcase) { ttw(ttr(TTrData, "} (" text ")\n")); return; }
213 #endif
214 #endif
215
216 // Inode -> Lost, Copying -> Inode, Lost -> Free
217 void block_commit(void)
218 {
219 int oldinodes = fs.inodes;
220
221 tw(tr(TR_BEGIN, TrIReclaim, "block_commit(%d -> %d) {\n",
222 oldinodes, fs.newinodes));
223 ttw(ttr(TTrRec, "block_commit(%d -> %d) {\n" NL,
224 oldinodes, fs.newinodes));
225
226 BLOCK_COMMIT_TEST(BLOCK_COMMIT_BEFORE, "Oops before commit");
227
228 block_flags_write(oldinodes, BF_LOST);
229
230 BLOCK_COMMIT_TEST(BLOCK_COMMIT_NO_VALID, "Oops no valid inode block");
231
232 // Validate new block as an inodes block
233 block_flags_write(fs.newinodes, BF_INODES);
234
235 bstat[fs.newinodes].lost = 0;
236 bstat[fs.newinodes].objects = 1;
237 inodes_set(fs.newinodes);
238
239 // Free old inodes block
240 block_free(oldinodes);
241
242 BLOCK_COMMIT_TEST(BLOCK_COMMIT_OLD_FREE, "Oops after freeing old block");
243
244 BLOCK_COMMIT_TEST(BLOCK_COMMIT_AFTER, "Oops after commit");
245
246 ttw(str(TTrRec, "} 0" NL));
247 tw(tr(TR_END, TrIReclaim, "}\n"));
248 }
249
250
251 /******************************************************************************
252 * Data Reclaim
253 ******************************************************************************/
254
255 // Important note: We must NOT perform a data reclaim when we are in the
256 // process of creating the journal file!
257
258 // Reclaim a data block, eg. move files to other blocks and erase old one.
259 // When the reclaim is done, we must completely delete the old inodes which
260 // are pointing into the old data sector which is going to be erased now.
261 iref_t data_reclaim(int space)
262 {
263 iref_t error;
264
265 tw(tr(TR_BEGIN, TrDReclaim, "data_reclaim(%d) {\n", space));
266
267 if (fs.initerror != EFFS_OK) {
268 tw(tr(TR_END, TrDReclaim, "} %d\n", fs.initerror));
269 return fs.initerror;
270 }
271
272 error = data_reclaim_try(space);
273
274 tw(tr(TR_END, TrDReclaim, "} (data_reclaim) %d\n", error));
275
276 return error;
277 }
278
279 int dage_max_reached(int dage_blk, int agegain)
280 {
281 int reclaim, early, log2, mask;
282
283 tw(tr(TR_BEGIN, TrDReclaim, "young(%d, %d) {\n", dage_blk, agegain));
284
285 // Simple algorithm
286 reclaim = (dage_blk + agegain - 2 * FFS_DAGE_MAX >= 0);
287
288 // Early exponential probability based reclaim
289 early = FFS_DAGE_MAX - dage_blk;
290 if (agegain > dage_blk - 4 && 0 < early && early <= FFS_DAGE_EARLY_WIDTH) {
291 if (early < 4)
292 early = 2;
293 if (early < FFS_DAGE_EARLY_WIDTH) {
294 // Now make an exponential probability distributon by
295 // generating a bitmask of a size relative to (dage_blk
296 // - DAGE_EARLY_WIDTH)
297 log2 = -1;
298 while (early > 0) {
299 early >>= 1;
300 log2++;
301 }
302 reclaim = log2;
303
304 mask = (1 << (log2 + 1)) - 1;
305 reclaim = ((rand() & mask) == 0);
306 }
307 }
308
309 // Do not perform a reclaim unless we gain a certain minimum
310 if (agegain < FFS_DAGE_GAIN_MIN)
311 reclaim = 0;
312
313 tw(tr(TR_END, TrDReclaim, "} (%d)\n", reclaim));
314 return reclaim;
315 }
316
317
318 // Try to reclaim at least <space> bytes of data space. On success, return
319 // the number of bytes actually reclaimed. Otherwise, on failure, return a
320 // (negative) error.
321 int data_reclaim_try(int space)
322 {
323 // 1. Find a suitable block to reclaim.
324 //
325 // 2. Relocate each valid object from old block (to another block). An
326 // object relocation is similar to a normal file update, e.g. similar to
327 // fupdate().
328 //
329 // 3. If there is not enough space to relocate a file, we must alloc a
330 // new block then data_format() it.
331 //
332 // 4. set BF_CLEANING flag of old block.
333 //
334 // 5. ALL inodes (also invalid an erased ones) referring into reclaimed
335 // block must now be totally wiped out.
336 //
337 // 6. Free (invalidate) old block.
338
339 int result = 0, reserved_ok = 0;
340 bref_t b, blocks_free;
341 bref_t brc_young_b, brc_lost_b, brc_unused_b;
342
343 blocksize_t brc_lost_lost, brc_lost_unused;
344 blocksize_t brc_unused_unused;
345 blocksize_t unused, unused_total, lost, lost_total, free;
346
347 age_t brc_young_dage, free_dage, dage;
348 struct block_header_s *bhp;
349 // Note gain can be negative if the free block is younger than the youngest data block
350 int age_gain;
351
352 tw(tr(TR_BEGIN, TrDReclaim, "data_reclaim_try(%d) {\n", space));
353 ttw(str(TTrRec, "drec{" NL));
354
355 // While searching for a block to reclaim, we maintain three block
356 // reclaim candidates (brc): One with the maximum number of lost bytes,
357 // one with the maximum number of unused bytes and another for the
358 // youngest block, e.g. the one with the largest age distance to
359 // fs.age_max. The candidates are tried in the order mentioned.
360
361 // This counts free blocks, so we initialize to number of blocks minus
362 // one for inodes.
363 blocks_free = dev.numblocks - 1;
364
365 // Initialize Block Reclaim Candidate (brc) variables
366 brc_lost_b = -1; brc_lost_unused = 0; brc_lost_lost = 0;
367 brc_unused_b = -1; brc_unused_unused = 0;
368
369 brc_young_b = -1; brc_young_dage = 0; free_dage = 0;
370
371 lost_total = 0;
372 unused_total = 0;
373
374 tw(tr(TR_FUNC, TrDReclaim,
375 "blk unused lost w/age age dist objs\n"));
376 for (b = 0; b < dev.numblocks; b++)
377 {
378 bhp = (struct block_header_s *) offset2addr(dev.binfo[b].offset);
379
380 if (is_block(b, BF_IS_DATA))
381 {
382 // Record number of lost bytes and number of unused bytes,
383 // eg. total space that would be freed if this block was
384 // reclaimed
385 lost = bstat[b].lost;
386 unused = dev.blocksize - (bstat[b].used - bstat[b].lost);
387 free = dev.blocksize - bstat[b].used;
388
389 lost_total += lost;
390 unused_total += unused;
391
392 if (free >= RESERVED_LOW)
393 reserved_ok = 1;
394 if (lost > brc_lost_lost) {
395 brc_lost_b = b;
396 brc_lost_lost = lost;
397 brc_lost_unused = unused;
398 }
399 if (unused > brc_unused_unused) {
400 brc_unused_b = b;
401 brc_unused_unused = unused;
402 }
403
404 tw(tr(TR_FUNC, TrDReclaim, "%3d %7d %7d ", b, unused, lost));
405
406 dage = saturate_dage(fs.age_max - bhp->age);
407
408 tw(tr(TR_NULL, TrDReclaim, "%6d %5d %4d %3d\n",
409 lost, bhp->age, dage, bstat[b].objects));
410
411 if (dage >= brc_young_dage) {
412 brc_young_b = b;
413 brc_young_dage = dage;
414 }
415 blocks_free--;
416 }
417 else if (is_block(b, BF_IS_FREE)) {
418 unused_total += dev.blocksize;
419
420 // Find youngest free block (in must cases we will only have one free b)
421 dage = saturate_dage(fs.age_max - bhp->age);
422
423 if (dage >= free_dage)
424 free_dage = dage; // Delta age of youngest free block
425 }
426 }
427 tw(tr(TR_FUNC, TrDReclaim, "sum %7d %7d\n", unused_total, lost_total));
428 tw(tr(TR_FUNC, TrDReclaim, "blocks_free = %d, fs.age_max = %d\n", blocks_free, fs.age_max));
429
430 age_gain = brc_young_dage - free_dage; // Same as free - block age
431
432 if (space > unused_total) {
433 // We will never be able to reclaim this amount...
434 result = 0;
435 }
436 else {
437 // No additional blocks (apart from spare block) are free...
438 tw(tr(TR_FUNC, TrDReclaim,
439 "brc_young_dage = %d, brc_lost_unused = %d, brc_unused_unused = %d\n",
440 brc_young_dage, brc_lost_unused, brc_unused_unused));
441
442 if (reserved_ok == 0) {
443 tw(tr(TR_FUNC, TrDReclaim,
444 "No reserved, reclaim most-lost block (%d)\n", brc_unused_b));
445 result = data_block_reclaim(brc_lost_b, MOST_LOST);
446 }
447 else if (dage_max_reached(brc_young_dage, age_gain) > 0 ) {
448 tw(tr(TR_FUNC, TrDReclaim, "Reclaiming youngest block (%d)\n",
449 brc_young_b));
450 result = data_block_reclaim(brc_young_b, YOUNGEST);
451 }
452 else if (brc_lost_unused >= space) {
453 tw(tr(TR_FUNC, TrDReclaim, "Reclaiming most-lost block (%d)\n",
454 brc_lost_b));
455 result = data_block_reclaim(brc_lost_b, MOST_LOST);
456 }
457 else if (brc_unused_unused >= space) {
458 tw(tr(TR_FUNC, TrDReclaim, "Reclaiming most-unused block (%d)\n",
459 brc_unused_b));
460 result = data_block_reclaim(brc_unused_b, MOST_UNUSED);
461 }
462 else {
463 tw(tr(TR_FUNC, TrDReclaim, "Reclaiming most-lost blockx (%d)\n",
464 brc_lost_b));
465 result = data_block_reclaim(brc_lost_b, MOST_LOST);
466 if (result >= 0)
467 result = 0; // We reclaimed a block but we still need more space
468 }
469
470 }
471 tw(tr(TR_END, TrDReclaim, "} (data_reclaim_try) %d\n", result));
472
473 return result;
474 }
475
476
477 #if (FFS_TEST == 0)
478 #define BLOCK_RECLAIM_TEST(testcase, text)
479 #else
480 #if (TARGET == 0)
481 // NOTEME: We have compressed the macro code because it will NOT compile on
482 // Unix otherwise. So until we find out why, we use this as a work-around.
483 #define BLOCK_RECLAIM_TEST(testcase, text) if (fs.testflags == testcase) { tw(tr(TR_FUNC, TrTestHigh, "(" text ")\n")); tw(tr(TR_END, TrDReclaim, "} (Test) -100\n", result));return -100; }
484 #else
485 #define BLOCK_RECLAIM_TEST(testcase, text) if (fs.testflags == testcase) { ttw(ttr(TTrData, "} (" text ")"NL)); ttw(ttr(TTrRec, "} (Test) -100" NL));return -100; }
486 #endif
487 #endif
488
489 #if (FFS_TEST == 0)
490 #define BLOCK_RECOVER_TEST_INIT(testcase, text)
491 #define BLOCK_RECOVER_TEST(testcase, text)
492 #else
493 #if (TARGET == 0)
494 #define BLOCK_RECOVER_TEST_INIT(testcase, text) int rand_object; if (fs.testflags == testcase) { rand_object = rand() % bstat[b].objects; tw(tr(TR_FUNC, TrTestHigh, "Fail when object nr %d is relocated\n", rand_object)); }
495
496 #define BLOCK_RECOVER_TEST(testcase, text) if (fs.testflags == testcase) {if (rand_object == n) { tw(tr(TR_FUNC, TrTestHigh, "(" text ")\n")); tw(tr(TR_END, TrDReclaim, "} (Test) -101\n", result)); return -101; } }
497
498 #else
499 #define BLOCK_RECOVER_TEST_INIT(testcase, text) int rand_object; if (fs.testflags == testcase) { rand_object = rand() % bstat[b].objects; ttw(ttr(TTrData, "Fail when object nr %d is relocated" NL, rand_object)); }
500 #define BLOCK_RECOVER_TEST(testcase, text) if (fs.testflags == testcase) {if (rand_object == n) { ttw(ttr(TTrData, "(" text ")" NL)); ttw(ttr(TTrRec, "} (Test) -101" NL, result)); return -101; } }
501 #endif
502 #endif
503
504 iref_t data_block_reclaim(bref_t b, int candidate)
505 {
506 iref_t i, n, j;
507 blocksize_t used_old, lost_old;
508 int org_res_space, result = 0;
509 iref_t org_block_files_reserved;
510 offset_t lower, upper;
511 struct inode_s *ip;
512 static int is_reclaim_running = 0;
513
514 tw(tr(TR_BEGIN, TrDReclaim, "data_block_reclaim(%d) {\n", b));
515
516 // In case of no free blocks (after sudden power off) or if the file
517 // system is near full we risk to be reentered (infinity recursively
518 // loop) and we can not allow that, so just return.
519 if (is_reclaim_running == 1) {
520 tw(tr(TR_END, TrDReclaim, "} (reenteret skip reclaim) 0\n"));
521 return EFFS_RECLAIMLOOP;
522 }
523
524 is_reclaim_running = 1;
525
526 // If there are more objects in this block than there are remaining
527 // free inodes, we have to make an inodes_reclaim() first.
528 tw(tr(TR_FUNC, TrDReclaim,
529 "block_objects, fs.inodes_max, inodes: used, free\n"));
530 tw(tr(TR_FUNC, TrDReclaim,
531 "%10d, %13d, %15d, %4d\n",
532 bstat[b].objects,
533 fs.inodes_max, bstat[fs.inodes].used,
534 fs.inodes_max - (bstat[fs.inodes].used + bstat[fs.inodes].lost)));
535
536 if (bstat[b].objects >= (fs.inodes_max - (bstat[fs.inodes].used +
537 bstat[fs.inodes].lost +
538 FFS_INODES_MARGIN))) {
539 tw(tr(TR_FUNC, TrInode, "NOTE: Will run out of free inodes...\n"));
540 inodes_reclaim();
541 }
542
543 // Allocate a new block. NOTE: we don't return an error because if we
544 // get in the situation where we don't have any free blocks this is the
545 // only way to recover.
546 if ((result = block_alloc(1, BF_DATA)) < 0) {
547 tw(tr(TR_FUNC, TrAll, "WARNING: block_alloc failed\n"));
548 }
549
550 BLOCK_RECLAIM_TEST(BLOCK_RECLAIM_ALLOC, "Oops after ffs_block_alloc()");
551
552 // If there are any objects at all to reclaim...
553 if (bstat[b].objects > 0)
554 {
555 BLOCK_RECOVER_TEST_INIT(BLOCK_RECOVER_OBJECTS, "Dummy")
556 // Save the current journal state
557 if (journal_push() != EFFS_OK) {
558 is_reclaim_running = 0; // NOTEME: change to goto?
559 return EFFS_CORRUPTED;
560 }
561
562 // We simulate that this block is completely full, such that we
563 // don't relocate files to the end of the block
564 used_old = bstat[b].used;
565 lost_old = bstat[b].lost; // For statistics
566 bstat[b].used = dev.blocksize - 1;
567
568
569 // Compute lower (inclusive) and upper (exclusive) bounds of the
570 // location of files in this block
571 lower = offset2location(dev.binfo[b].offset);
572 upper = offset2location(dev.binfo[b].offset + dev.blocksize);
573
574 tw(tr(TR_FUNC, TrDReclaim, "Block addr range = 0x%X..0x%X\n",
575 location2offset(lower), location2offset(upper)));
576
577 // This is the only time we are allowed to use the reserved
578 org_block_files_reserved= fs.block_files_reserved;
579 fs.block_files_reserved = 0;
580
581 org_res_space = fs.reserved_space;
582 fs.reserved_space = RESERVED_NONE;
583
584 ip = inode_addr(1);
585 for (i = 1, n = 0; i < fs.inodes_max; i++, ip++)
586 {
587 BLOCK_RECOVER_TEST(BLOCK_RECOVER_OBJECTS, "Oops before relocate all objects");
588 // Ensure object is valid and within the block to be reclaimed
589 if (is_object_valid(ip) &&
590 lower <= ip->location && ip->location < upper)
591 {
592 if ((result = object_relocate(i)) < 0) {
593 tw(tr(TR_FUNC, TrAll, "FATAL object_relocate failed\n"));
594 break;
595 }
596
597 // If we reclaim a segment head or wch that is in use we must
598 // update the file descriptor as well
599 for (j = 0; j < fs.fd_max; j++) {
600 if (i == fs.fd[j].seghead) {
601 tw(tr(TR_FUNC, TrDReclaim,
602 "Updated seghead %d -> %d \n",
603 fs.fd[j].seghead, result));
604 fs.fd[j].seghead = result;
605 }
606 if (i == fs.fd[j].wch) {
607 tw(tr(TR_FUNC, TrDReclaim,
608 "Updated wch %d -> %d \n",
609 fs.fd[j].wch, result));
610 fs.fd[j].wch = result;
611 }
612 }
613
614 // If we have just reclaimed an object which we started on
615 // updating we must also update ojournal
616 if (i == fs.ojournal.oldi) {
617 struct inode_s *ip = inode_addr(result);
618 tw(tr(TR_FUNC, TrDReclaim,
619 "Updated ojournal oldi %d -> %d \n",
620 fs.ojournal.oldi, result));
621 fs.ojournal.oldi = result;
622 fs.ojournal.location = ip->location;
623 }
624
625 if (i == fs.ojournal.diri || i == -fs.ojournal.diri) {
626 fs.ojournal.diri = (fs.ojournal.diri < 0 ? -result : result);
627 tw(tr(TR_FUNC, TrDReclaim,
628 "Updated ojournal: diri %d -> %d \n",
629 i, fs.ojournal.diri));
630 }
631
632 if (i == fs.ojournal.repli || i == -fs.ojournal.repli) {
633 fs.ojournal.repli = (fs.ojournal.repli < 0 ? -result : result);
634 tw(tr(TR_FUNC, TrDReclaim,
635 "Updated ojournal: repli %d -> %d \n",
636 i, fs.ojournal.repli));
637 }
638
639 if (i == fs.i_backup || i == -fs.i_backup) {
640 fs.i_backup = (fs.i_backup < 0 ? -result : result);
641 tw(tr(TR_FUNC, TrDReclaim,
642 "Updated i_backup: %d -> %d \n", i, fs.i_backup));
643 }
644
645 n++;
646 }
647 }
648
649 fs.block_files_reserved = org_block_files_reserved; // Restore
650 fs.reserved_space = org_res_space;
651
652 tw(tr(TR_FUNC, TrDReclaim, "Reclaimed %d objects\n", n));
653 if (result >= 0)
654 result = n; // We return number of objects relocated
655
656 if (i < fs.inodes_max) {
657 // We did not finish, so restore the old bstat[].used of the block.
658 bstat[b].used = used_old;
659 tw(tr(TR_FUNC, TrAll,
660 "WARNING: data_block_reclaim() not completed\n"));
661 result = EFFS_DBR;
662 }
663
664 // Restore the saved journal state
665 if (journal_pop() != EFFS_OK) {
666 is_reclaim_running = 0; // NOTEME: change to goto?
667 return EFFS_CORRUPTED;
668 }
669 }
670 BLOCK_RECLAIM_TEST(BLOCK_RECLAIM_NO_CLEAN, "Oops before clean old data block");
671
672 if (result >= 0) {
673 // Clean the block (remove all inodes that refer to this block)
674 block_flags_write(b, BF_CLEANING);
675 block_clean(b);
676
677 statistics_update_drec(used_old - lost_old, lost_old, candidate);
678
679 BLOCK_RECLAIM_TEST(BLOCK_RECLAIM_CLEANING, "Oops before free old data block");
680
681 // Free the old block
682 block_free(b);
683 }
684
685 is_reclaim_running = 0;
686
687 tw(tr(TR_END, TrDReclaim, "} (data_block_reclaim) %d\n", result));
688 ttw(ttr(TTrRec, "} %d" NL, result));
689
690 return result;
691 }
692
693 // Relocate object represented by inode reference <i>.
694 iref_t object_relocate(iref_t oldi)
695 {
696 iref_t newi;
697 struct inode_s *oldip;
698 char *olddata, *oldname;
699 int oldsize;
700
701 tw(tr(TR_BEGIN, TrReclaimLow, "object_relocate(%d) {\n", oldi));
702
703 journal_begin(oldi);
704
705 oldip = inode_addr(oldi);
706
707 oldsize = segment_datasize(oldip);
708 olddata = offset2addr(location2offset(oldip->location));
709 oldname = addr2name(olddata);
710 olddata = addr2data(olddata, oldip);
711
712 if (is_object(oldip, OT_SEGMENT))
713 newi = segment_create(olddata, oldsize, -oldi);
714 else {
715 // root inode is a special case
716 if (*oldname == '/')
717 newi = object_create(oldname, olddata, oldsize, 0);
718 else
719 newi = object_create(oldname, olddata, oldsize, oldi);
720 }
721
722 if (newi < 0) {
723 tw(tr(TR_END, TrReclaimLow, "} %d\n", newi));
724 return newi;
725 }
726
727 // root inode is a special case
728 if ((*oldname == '/') && !is_object(oldip, OT_SEGMENT)) {
729 tw(tr(TR_FUNC, TrDReclaim, "Relocating fs.root: %d->%d\n", oldi, newi));
730 fs.root = newi;
731 }
732
733 journal_end(0);
734
735 tw(tr(TR_END, TrReclaimLow, "} %d\n", newi));
736
737 return newi;
738 }
739
740 // Clean a block, eg. erase all inodes that refer to this block.
741 iref_t block_clean(bref_t b)
742 {
743 iref_t i, n;
744 struct inode_s *ip;
745 offset_t lower, upper;
746
747 tw(tr(TR_FUNC, TrDReclaim, "block_clean(%d) { ", b));
748
749 // Compute lower (inclusive) and upper (exclusive) bounds of the
750 // location of files in this block
751 lower = offset2location(dev.binfo[b].offset);
752 upper = offset2location(dev.binfo[b].offset + dev.blocksize);
753
754 tw(tr(TR_FUNC, TrDReclaim, "offset range = 0x%X..0x%X: ", lower, upper));
755
756 ip = inode_addr(1);
757 for (i = 1, n = 0; i < fs.inodes_max; i++, ip++)
758 {
759 // Ensure object is within the block to be reclaimed. Note: if ffs
760 // is conf. with 1MB or above will all not used inodes default have
761 // the location to FFFF which will trigger a clean and make a error!
762 if (lower <= ip->location && upper > ip->location)
763 {
764 tw(tr(TR_NULL, TrReclaimLow, "%d ", i));
765 // Set the size to zero so it won't be counted in ffs_initialize()
766 ffsdrv.write_halfword((uint16 *) &ip->size, 0);
767 n++;
768 }
769 }
770 tw(tr(TR_NULL, TrDReclaim, "} %d\n", n));
771
772 return n;
773 }
774
775
776 /******************************************************************************
777 * Main and block reclaim
778 ******************************************************************************/
779
780 // Reclaim (erase) all blocks that are marked as invalid/reclaimable. Each
781 // time a block is erased, its age is incremented so as to support wear
782 // levelling. Also, the global age limits are updated. FIXME: Should we
783 // avoid having ffs_initialize() do a block_reclaim() because it delays reboot?.
784 int blocks_reclaim(void)
785 {
786 bref_t b, n, b_lost_space;
787 int blocks_free = 0, lost_space;
788
789 int free_space, b_free_space;
790
791 tw(tr(TR_BEGIN, TrBlock, "blocks_reclaim() {\n"));
792 ttw(str(TTrRec, "blocks_reclaim() {" NL));
793
794 // Testing of fs.testflags is for the sake of testing block_commit()
795 if ((fs.testflags & BLOCK_COMMIT_BASE) != 0) {
796 tw(tr(TR_FUNC, TrBlock, "Bailing out because fs.testflags = 0x%X\n",
797 fs.testflags));
798 }
799 else {
800 for (b = 0, n = 0; b < dev.numblocks; b++) {
801 if (is_block_flag(b, BF_LOST)) {
802 block_reclaim(b);
803 n++;
804 }
805 if (is_block(b, BF_IS_FREE)) {
806 blocks_free++;
807 }
808 }
809 }
810
811 // If the number of free blocks is less than fs.blocks_free_min we
812 // call data_block_reclaim(). We will reclaim the block with most lost
813 // space. This should only happend if we got a sudden power off/reset
814 // while we reclaimed a block.
815 if (blocks_free < fs.blocks_free_min) {
816 lost_space = 0;
817 free_space = 0;
818
819 // We most never reclaim the block with most free space because this
820 // is the only block we can relocate the objects to.
821 for (b = 0; b < dev.numblocks; b++) {
822 if (is_block_flag(b, BF_DATA)) {
823 if ((dev.blocksize - bstat[b].used) > free_space) {
824 free_space = dev.blocksize - bstat[b].used;
825 b_free_space = b;
826 }
827 }
828 }
829 tw(tr(TR_FUNC, TrBlock, "most free space: %d in block: %d \n",
830 free_space, b_free_space));
831
832 for (b = 0; b < dev.numblocks; b++) {
833 if (is_block_flag(b, BF_DATA) && b != b_free_space) {
834 if (bstat[b].lost > lost_space) {
835 lost_space = bstat[b].lost;
836 b_lost_space = b;
837 }
838 }
839 }
840 tw(tr(TR_FUNC, TrBlock, "most lost space: %d in block: %d \n",
841 lost_space, b_lost_space));
842
843 data_block_reclaim(b_lost_space, MOST_LOST);
844 }
845 tw(tr(TR_END, TrBlock, "} %d\n", n));
846 ttw(ttr(TTrRec, "} %d" NL, n));
847
848 return n;
849 }
850
851 int block_reclaim(bref_t b)
852 {
853 age_t age;
854 struct block_header_s *bhp;
855
856 tw(tr(TR_BEGIN, TrBlock, "block_reclaim(%d) {\n", b));
857
858 // In ffs_initialize() we set fs.initerror = EFFS_INVALID while we call
859 // blocks_fsck(). We test for that condition now, in order to avoid
860 // doing sector erases that will delay the whole target boot process.
861 if (fs.initerror == EFFS_INVALID) {
862 tw(tr(TR_END, TrBlock, "} %d\n", fs.initerror));
863 return fs.initerror;
864 }
865
866 // Testing of fs.testflags is for the sake of testing block_commit()
867 if ((fs.testflags & BLOCK_COMMIT_BASE) != 0 &&
868 fs.testflags != BLOCK_COMMIT_OLD_FREE) {
869 tw(tr(TR_FUNC, TrBlock, "Bailing out because fs.testflags = 0x%X\n",
870 fs.testflags));
871 }
872 else {
873 // We must read block's age before we erase it.
874 bhp = (struct block_header_s *) offset2addr(dev.binfo[b].offset);
875 age = bhp->age;
876 ffsdrv.erase(b);
877 block_preformat(b, age);
878 }
879
880 tw(tr(TR_END, TrBlock, "} %d\n", 0));
881
882 return 0;
883 }