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