yaffs: More clean up
[yaffs2.git] / yaffs_guts.c
1 /*
2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
3  *
4  * Copyright (C) 2002-2010 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 "yportenv.h"
15 #include "yaffs_trace.h"
16
17 #include "yaffs_guts.h"
18 #include "yaffs_tagsvalidity.h"
19 #include "yaffs_getblockinfo.h"
20
21 #include "yaffs_tagscompat.h"
22
23 #include "yaffs_nand.h"
24
25 #include "yaffs_yaffs1.h"
26 #include "yaffs_yaffs2.h"
27 #include "yaffs_bitmap.h"
28 #include "yaffs_verify.h"
29
30 #include "yaffs_nand.h"
31 #include "yaffs_packedtags2.h"
32
33 #include "yaffs_nameval.h"
34 #include "yaffs_allocator.h"
35
36 #include "yaffs_attribs.h"
37
38 /* Note YAFFS_GC_GOOD_ENOUGH must be <= YAFFS_GC_PASSIVE_THRESHOLD */
39 #define YAFFS_GC_GOOD_ENOUGH 2
40 #define YAFFS_GC_PASSIVE_THRESHOLD 4
41
42 #include "yaffs_ecc.h"
43
44
45
46 /* Robustification (if it ever comes about...) */
47 static void yaffs_retire_block(struct yaffs_dev *dev, int flash_block);
48 static void yaffs_handle_chunk_wr_error(struct yaffs_dev *dev, int nand_chunk,
49                 int erased_ok);
50 static void yaffs_handle_chunk_wr_ok(struct yaffs_dev *dev, int nand_chunk,
51                                 const u8 *data,
52                                 const struct yaffs_ext_tags *tags);
53 static void yaffs_handle_chunk_update(struct yaffs_dev *dev, int nand_chunk,
54                                 const struct yaffs_ext_tags *tags);
55
56 /* Other local prototypes */
57 static void yaffs_update_parent(struct yaffs_obj *obj);
58 static int yaffs_unlink_obj(struct yaffs_obj *obj);
59 static int yaffs_obj_cache_dirty(struct yaffs_obj *obj);
60
61 static int yaffs_write_new_chunk(struct yaffs_dev *dev,
62                                         const u8 *buffer,
63                                         struct yaffs_ext_tags *tags,
64                                         int use_reserver);
65
66
67 static struct yaffs_obj *yaffs_new_obj(struct yaffs_dev *dev, int number,
68                                         enum yaffs_obj_type type);
69
70
71 static int yaffs_apply_xattrib_mod(struct yaffs_obj *obj, char *buffer, struct yaffs_xattr_mod *xmod);
72
73 static void yaffs_remove_obj_from_dir(struct yaffs_obj *obj);
74 static int yaffs_generic_obj_del(struct yaffs_obj *in);
75
76 static int yaffs_check_chunk_erased(struct yaffs_dev *dev,
77                                 int nand_chunk);
78
79 static int yaffs_unlink_worker(struct yaffs_obj *obj);
80
81 static int yaffs_tags_match(const struct yaffs_ext_tags *tags, int obj_id,
82                         int chunk_obj);
83
84 static int yaffs_alloc_chunk(struct yaffs_dev *dev, int use_reserver,
85                                 struct yaffs_block_info **block_ptr);
86
87 static void yaffs_check_obj_details_loaded(struct yaffs_obj *in);
88
89 static void yaffs_invalidate_whole_cache(struct yaffs_obj *in);
90 static void yaffs_invalidate_chunk_cache(struct yaffs_obj *object, int chunk_id);
91
92 static int yaffs_find_chunk_in_file(struct yaffs_obj *in, int inode_chunk,
93                                 struct yaffs_ext_tags *tags);
94
95 static int yaffs_verify_chunk_written(struct yaffs_dev *dev,
96                                         int nand_chunk,
97                                         const u8 *data,
98                                         struct yaffs_ext_tags *tags);
99
100
101 static void yaffs_load_name_from_oh(struct yaffs_dev *dev,YCHAR *name, const YCHAR *oh_name, int buff_size);
102 static void yaffs_load_oh_from_name(struct yaffs_dev *dev,YCHAR *oh_name, const YCHAR *name);
103
104
105 /* Function to calculate chunk and offset */
106
107 static void yaffs_addr_to_chunk(struct yaffs_dev *dev, loff_t addr, int *chunk_out,
108                 u32 *offset_out)
109 {
110         int chunk;
111         u32 offset;
112
113         chunk  = (u32)(addr >> dev->chunk_shift);
114
115         if (dev->chunk_div == 1) {
116                 /* easy power of 2 case */
117                 offset = (u32)(addr & dev->chunk_mask);
118         } else {
119                 /* Non power-of-2 case */
120
121                 loff_t chunk_base;
122
123                 chunk /= dev->chunk_div;
124
125                 chunk_base = ((loff_t)chunk) * dev->data_bytes_per_chunk;
126                 offset = (u32)(addr - chunk_base);
127         }
128
129         *chunk_out = chunk;
130         *offset_out = offset;
131 }
132
133 /* Function to return the number of shifts for a power of 2 greater than or
134  * equal to the given number
135  * Note we don't try to cater for all possible numbers and this does not have to
136  * be hellishly efficient.
137  */
138
139 static u32 calc_shifts_ceiling(u32 x)
140 {
141         int extra_bits;
142         int shifts;
143
144         shifts = extra_bits = 0;
145
146         while (x > 1) {
147                 if (x & 1)
148                         extra_bits++;
149                 x >>= 1;
150                 shifts++;
151         }
152
153         if (extra_bits)
154                 shifts++;
155
156         return shifts;
157 }
158
159 /* Function to return the number of shifts to get a 1 in bit 0
160  */
161
162 static u32 calc_shifts(u32 x)
163 {
164         u32 shifts;
165
166         shifts =  0;
167
168         if (!x)
169                 return 0;
170
171         while (!(x&1)) {
172                 x >>= 1;
173                 shifts++;
174         }
175
176         return shifts;
177 }
178
179
180
181 /*
182  * Temporary buffer manipulations.
183  */
184
185 static int yaffs_init_tmp_buffers(struct yaffs_dev *dev)
186 {
187         int i;
188         u8 *buf = (u8 *)1;
189
190         memset(dev->temp_buffer, 0, sizeof(dev->temp_buffer));
191
192         for (i = 0; buf && i < YAFFS_N_TEMP_BUFFERS; i++) {
193                 dev->temp_buffer[i].line = 0;   /* not in use */
194                 dev->temp_buffer[i].buffer = buf =
195                     YMALLOC_DMA(dev->param.total_bytes_per_chunk);
196         }
197
198         return buf ? YAFFS_OK : YAFFS_FAIL;
199 }
200
201 u8 *yaffs_get_temp_buffer(struct yaffs_dev *dev, int line_no)
202 {
203         int i, j;
204
205         dev->temp_in_use++;
206         if (dev->temp_in_use > dev->max_temp)
207                 dev->max_temp = dev->temp_in_use;
208
209         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
210                 if (dev->temp_buffer[i].line == 0) {
211                         dev->temp_buffer[i].line = line_no;
212                         if ((i + 1) > dev->max_temp) {
213                                 dev->max_temp = i + 1;
214                                 for (j = 0; j <= i; j++)
215                                         dev->temp_buffer[j].max_line =
216                                             dev->temp_buffer[j].line;
217                         }
218
219                         return dev->temp_buffer[i].buffer;
220                 }
221         }
222
223         T(YAFFS_TRACE_BUFFERS,
224           (TSTR("Out of temp buffers at line %d, other held by lines:"),
225            line_no));
226         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++)
227                 T(YAFFS_TRACE_BUFFERS, (TSTR(" %d "), dev->temp_buffer[i].line));
228
229         T(YAFFS_TRACE_BUFFERS, (TSTR(" " TENDSTR)));
230
231         /*
232          * If we got here then we have to allocate an unmanaged one
233          * This is not good.
234          */
235
236         dev->unmanaged_buffer_allocs++;
237         return YMALLOC(dev->data_bytes_per_chunk);
238
239 }
240
241 void yaffs_release_temp_buffer(struct yaffs_dev *dev, u8 *buffer,
242                                     int line_no)
243 {
244         int i;
245
246         dev->temp_in_use--;
247
248         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
249                 if (dev->temp_buffer[i].buffer == buffer) {
250                         dev->temp_buffer[i].line = 0;
251                         return;
252                 }
253         }
254
255         if (buffer) {
256                 /* assume it is an unmanaged one. */
257                 T(YAFFS_TRACE_BUFFERS,
258                   (TSTR("Releasing unmanaged temp buffer in line %d" TENDSTR),
259                    line_no));
260                 YFREE(buffer);
261                 dev->unmanaged_buffer_deallocs++;
262         }
263
264 }
265
266 /*
267  * Determine if we have a managed buffer.
268  */
269 int yaffs_is_managed_tmp_buffer(struct yaffs_dev *dev, const u8 *buffer)
270 {
271         int i;
272
273         for (i = 0; i < YAFFS_N_TEMP_BUFFERS; i++) {
274                 if (dev->temp_buffer[i].buffer == buffer)
275                         return 1;
276         }
277
278         for (i = 0; i < dev->param.n_caches; i++) {
279                 if (dev->cache[i].data == buffer)
280                         return 1;
281         }
282
283         if (buffer == dev->checkpt_buffer)
284                 return 1;
285
286         T(YAFFS_TRACE_ALWAYS,
287                 (TSTR("yaffs: unmaged buffer detected.\n" TENDSTR)));
288         return 0;
289 }
290
291 /*
292  * Verification code
293  */
294
295
296
297
298 /*
299  *  Simple hash function. Needs to have a reasonable spread
300  */
301
302 static Y_INLINE int yaffs_hash_fn(int n)
303 {
304         n = abs(n);
305         return n % YAFFS_NOBJECT_BUCKETS;
306 }
307
308 /*
309  * Access functions to useful fake objects.
310  * Note that root might have a presence in NAND if permissions are set.
311  */
312
313 struct yaffs_obj *yaffs_root(struct yaffs_dev *dev)
314 {
315         return dev->root_dir;
316 }
317
318 struct yaffs_obj *yaffs_lost_n_found(struct yaffs_dev *dev)
319 {
320         return dev->lost_n_found;
321 }
322
323
324 /*
325  *  Erased NAND checking functions
326  */
327
328 int yaffs_check_ff(u8 *buffer, int n_bytes)
329 {
330         /* Horrible, slow implementation */
331         while (n_bytes--) {
332                 if (*buffer != 0xFF)
333                         return 0;
334                 buffer++;
335         }
336         return 1;
337 }
338
339 static int yaffs_check_chunk_erased(struct yaffs_dev *dev,
340                                 int nand_chunk)
341 {
342         int retval = YAFFS_OK;
343         u8 *data = yaffs_get_temp_buffer(dev, __LINE__);
344         struct yaffs_ext_tags tags;
345         int result;
346
347         result = yaffs_rd_chunk_tags_nand(dev, nand_chunk, data, &tags);
348
349         if (tags.ecc_result > YAFFS_ECC_RESULT_NO_ERROR)
350                 retval = YAFFS_FAIL;
351
352         if (!yaffs_check_ff(data, dev->data_bytes_per_chunk) || tags.chunk_used) {
353                 T(YAFFS_TRACE_NANDACCESS,
354                   (TSTR("Chunk %d not erased" TENDSTR), nand_chunk));
355                 retval = YAFFS_FAIL;
356         }
357
358         yaffs_release_temp_buffer(dev, data, __LINE__);
359
360         return retval;
361
362 }
363
364
365 static int yaffs_verify_chunk_written(struct yaffs_dev *dev,
366                                         int nand_chunk,
367                                         const u8 *data,
368                                         struct yaffs_ext_tags *tags)
369 {
370         int retval = YAFFS_OK;
371         struct yaffs_ext_tags temp_tags;
372         u8 *buffer = yaffs_get_temp_buffer(dev,__LINE__);
373         int result;
374         
375         result = yaffs_rd_chunk_tags_nand(dev,nand_chunk,buffer,&temp_tags);
376         if(memcmp(buffer,data,dev->data_bytes_per_chunk) ||
377                 temp_tags.obj_id != tags->obj_id ||
378                 temp_tags.chunk_id  != tags->chunk_id ||
379                 temp_tags.n_bytes != tags->n_bytes)
380                 retval = YAFFS_FAIL;
381
382         yaffs_release_temp_buffer(dev, buffer, __LINE__);
383
384         return retval;
385 }
386
387 static int yaffs_write_new_chunk(struct yaffs_dev *dev,
388                                         const u8 *data,
389                                         struct yaffs_ext_tags *tags,
390                                         int use_reserver)
391 {
392         int attempts = 0;
393         int write_ok = 0;
394         int chunk;
395
396         yaffs2_checkpt_invalidate(dev);
397
398         do {
399                 struct yaffs_block_info *bi = 0;
400                 int erased_ok = 0;
401
402                 chunk = yaffs_alloc_chunk(dev, use_reserver, &bi);
403                 if (chunk < 0) {
404                         /* no space */
405                         break;
406                 }
407
408                 /* First check this chunk is erased, if it needs
409                  * checking.  The checking policy (unless forced
410                  * always on) is as follows:
411                  *
412                  * Check the first page we try to write in a block.
413                  * If the check passes then we don't need to check any
414                  * more.        If the check fails, we check again...
415                  * If the block has been erased, we don't need to check.
416                  *
417                  * However, if the block has been prioritised for gc,
418                  * then we think there might be something odd about
419                  * this block and stop using it.
420                  *
421                  * Rationale: We should only ever see chunks that have
422                  * not been erased if there was a partially written
423                  * chunk due to power loss.  This checking policy should
424                  * catch that case with very few checks and thus save a
425                  * lot of checks that are most likely not needed.
426                  *
427                  * Mods to the above
428                  * If an erase check fails or the write fails we skip the 
429                  * rest of the block.
430                  */
431
432                 /* let's give it a try */
433                 attempts++;
434
435                 if(dev->param.always_check_erased)
436                         bi->skip_erased_check = 0;
437
438                 if (!bi->skip_erased_check) {
439                         erased_ok = yaffs_check_chunk_erased(dev, chunk);
440                         if (erased_ok != YAFFS_OK) {
441                                 T(YAFFS_TRACE_ERROR,
442                                 (TSTR("**>> yaffs chunk %d was not erased"
443                                 TENDSTR), chunk));
444
445                                 /* If not erased, delete this one,
446                                  * skip rest of block and
447                                  * try another chunk */
448                                  yaffs_chunk_del(dev,chunk,1,__LINE__);
449                                  yaffs_skip_rest_of_block(dev);
450                                 continue;
451                         }
452                 }
453
454                 write_ok = yaffs_wr_chunk_tags_nand(dev, chunk,
455                                 data, tags);
456
457                 if(!bi->skip_erased_check)
458                         write_ok = yaffs_verify_chunk_written(dev, chunk, data, tags);
459
460                 if (write_ok != YAFFS_OK) {
461                         /* Clean up aborted write, skip to next block and
462                          * try another chunk */
463                         yaffs_handle_chunk_wr_error(dev, chunk, erased_ok);
464                         continue;
465                 }
466
467                 bi->skip_erased_check = 1;
468
469                 /* Copy the data into the robustification buffer */
470                 yaffs_handle_chunk_wr_ok(dev, chunk, data, tags);
471
472         } while (write_ok != YAFFS_OK &&
473                 (yaffs_wr_attempts <= 0 || attempts <= yaffs_wr_attempts));
474
475         if (!write_ok)
476                 chunk = -1;
477
478         if (attempts > 1) {
479                 T(YAFFS_TRACE_ERROR,
480                         (TSTR("**>> yaffs write required %d attempts" TENDSTR),
481                         attempts));
482
483                 dev->n_retired_writes += (attempts - 1);
484         }
485
486         return chunk;
487 }
488
489
490  
491 /*
492  * Block retiring for handling a broken block.
493  */
494
495 static void yaffs_retire_block(struct yaffs_dev *dev, int flash_block)
496 {
497         struct yaffs_block_info *bi = yaffs_get_block_info(dev, flash_block);
498
499         yaffs2_checkpt_invalidate(dev);
500         
501         yaffs2_clear_oldest_dirty_seq(dev,bi);
502
503         if (yaffs_mark_bad(dev, flash_block) != YAFFS_OK) {
504                 if (yaffs_erase_block(dev, flash_block) != YAFFS_OK) {
505                         T(YAFFS_TRACE_ALWAYS, (TSTR(
506                                 "yaffs: Failed to mark bad and erase block %d"
507                                 TENDSTR), flash_block));
508                 } else {
509                         struct yaffs_ext_tags tags;
510                         int chunk_id = flash_block * dev->param.chunks_per_block;
511
512                         u8 *buffer = yaffs_get_temp_buffer(dev, __LINE__);
513
514                         memset(buffer, 0xff, dev->data_bytes_per_chunk);
515                         yaffs_init_tags(&tags);
516                         tags.seq_number = YAFFS_SEQUENCE_BAD_BLOCK;
517                         if (dev->param.write_chunk_tags_fn(dev, chunk_id -
518                                 dev->chunk_offset, buffer, &tags) != YAFFS_OK)
519                                 T(YAFFS_TRACE_ALWAYS, (TSTR("yaffs: Failed to "
520                                         TCONT("write bad block marker to block %d")
521                                         TENDSTR), flash_block));
522
523                         yaffs_release_temp_buffer(dev, buffer, __LINE__);
524                 }
525         }
526
527         bi->block_state = YAFFS_BLOCK_STATE_DEAD;
528         bi->gc_prioritise = 0;
529         bi->needs_retiring = 0;
530
531         dev->n_retired_blocks++;
532 }
533
534 /*
535  * Functions for robustisizing TODO
536  *
537  */
538
539 static void yaffs_handle_chunk_wr_ok(struct yaffs_dev *dev, int nand_chunk,
540                                 const u8 *data,
541                                 const struct yaffs_ext_tags *tags)
542 {
543         dev=dev;
544         nand_chunk=nand_chunk;
545         data=data;
546         tags=tags;
547 }
548
549 static void yaffs_handle_chunk_update(struct yaffs_dev *dev, int nand_chunk,
550                                 const struct yaffs_ext_tags *tags)
551 {
552         dev=dev;
553         nand_chunk=nand_chunk;
554         tags=tags;
555 }
556
557 void yaffs_handle_chunk_error(struct yaffs_dev *dev, struct yaffs_block_info *bi)
558 {
559         if (!bi->gc_prioritise) {
560                 bi->gc_prioritise = 1;
561                 dev->has_pending_prioritised_gc = 1;
562                 bi->chunk_error_strikes++;
563
564                 if (bi->chunk_error_strikes > 3) {
565                         bi->needs_retiring = 1; /* Too many stikes, so retire this */
566                         T(YAFFS_TRACE_ALWAYS, (TSTR("yaffs: Block struck out" TENDSTR)));
567
568                 }
569         }
570 }
571
572 static void yaffs_handle_chunk_wr_error(struct yaffs_dev *dev, int nand_chunk,
573                 int erased_ok)
574 {
575         int flash_block = nand_chunk / dev->param.chunks_per_block;
576         struct yaffs_block_info *bi = yaffs_get_block_info(dev, flash_block);
577
578         yaffs_handle_chunk_error(dev, bi);
579
580         if (erased_ok) {
581                 /* Was an actual write failure, so mark the block for retirement  */
582                 bi->needs_retiring = 1;
583                 T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
584                   (TSTR("**>> Block %d needs retiring" TENDSTR), flash_block));
585         }
586
587         /* Delete the chunk */
588         yaffs_chunk_del(dev, nand_chunk, 1, __LINE__);
589         yaffs_skip_rest_of_block(dev);
590 }
591
592
593 /*---------------- Name handling functions ------------*/
594
595 static u16 yaffs_calc_name_sum(const YCHAR *name)
596 {
597         u16 sum = 0;
598         u16 i = 1;
599
600         const YUCHAR *bname = (const YUCHAR *) name;
601         if (bname) {
602                 while ((*bname) && (i < (YAFFS_MAX_NAME_LENGTH/2))) {
603
604                         /* 0x1f mask is case insensitive */
605                         sum += ((*bname) & 0x1f) * i;
606                         i++;
607                         bname++;
608                 }
609         }
610         return sum;
611 }
612
613 void yaffs_set_obj_name(struct yaffs_obj *obj, const YCHAR *name)
614 {
615 #ifdef CONFIG_YAFFS_SHORT_NAMES_IN_RAM
616         memset(obj->short_name, 0, sizeof(YCHAR) * (YAFFS_SHORT_NAME_LENGTH+1));
617         if (name && yaffs_strnlen(name,YAFFS_SHORT_NAME_LENGTH+1) <= YAFFS_SHORT_NAME_LENGTH)
618                 yaffs_strcpy(obj->short_name, name);
619         else
620                 obj->short_name[0] = _Y('\0');
621 #endif
622         obj->sum = yaffs_calc_name_sum(name);
623 }
624
625 void yaffs_set_obj_name_from_oh(struct yaffs_obj *obj, const struct yaffs_obj_hdr *oh)
626 {
627 #ifdef CONFIG_YAFFS_AUTO_UNICODE
628         YCHAR tmp_name[YAFFS_MAX_NAME_LENGTH+1];
629         memset(tmp_name,0,sizeof(tmp_name));
630         yaffs_load_name_from_oh(obj->my_dev,tmp_name,oh->name,YAFFS_MAX_NAME_LENGTH+1);
631         yaffs_set_obj_name(obj,tmp_name);
632 #else
633         yaffs_set_obj_name(obj,oh->name);
634 #endif
635 }
636
637 /*-------------------- TNODES -------------------
638
639  * List of spare tnodes
640  * The list is hooked together using the first pointer
641  * in the tnode.
642  */
643
644
645 struct yaffs_tnode *yaffs_get_tnode(struct yaffs_dev *dev)
646 {
647         struct yaffs_tnode *tn = yaffs_alloc_raw_tnode(dev);
648         if (tn){
649                 memset(tn, 0, dev->tnode_size);
650                 dev->n_tnodes++;
651         }
652
653         dev->checkpoint_blocks_required = 0; /* force recalculation*/
654
655         return tn;
656 }
657
658 /* FreeTnode frees up a tnode and puts it back on the free list */
659 static void yaffs_free_tnode(struct yaffs_dev *dev, struct yaffs_tnode *tn)
660 {
661         yaffs_free_raw_tnode(dev,tn);
662         dev->n_tnodes--;
663         dev->checkpoint_blocks_required = 0; /* force recalculation*/
664 }
665
666 static void yaffs_deinit_tnodes_and_objs(struct yaffs_dev *dev)
667 {
668         yaffs_deinit_raw_tnodes_and_objs(dev);
669         dev->n_obj = 0;
670         dev->n_tnodes = 0;
671 }
672
673
674 void yaffs_load_tnode_0(struct yaffs_dev *dev, struct yaffs_tnode *tn, unsigned pos,
675                 unsigned val)
676 {
677         u32 *map = (u32 *)tn;
678         u32 bit_in_map;
679         u32 bit_in_word;
680         u32 word_in_map;
681         u32 mask;
682
683         pos &= YAFFS_TNODES_LEVEL0_MASK;
684         val >>= dev->chunk_grp_bits;
685
686         bit_in_map = pos * dev->tnode_width;
687         word_in_map = bit_in_map / 32;
688         bit_in_word = bit_in_map & (32 - 1);
689
690         mask = dev->tnode_mask << bit_in_word;
691
692         map[word_in_map] &= ~mask;
693         map[word_in_map] |= (mask & (val << bit_in_word));
694
695         if (dev->tnode_width > (32 - bit_in_word)) {
696                 bit_in_word = (32 - bit_in_word);
697                 word_in_map++;;
698                 mask = dev->tnode_mask >> (/*dev->tnode_width -*/ bit_in_word);
699                 map[word_in_map] &= ~mask;
700                 map[word_in_map] |= (mask & (val >> bit_in_word));
701         }
702 }
703
704 u32 yaffs_get_group_base(struct yaffs_dev *dev, struct yaffs_tnode *tn,
705                 unsigned pos)
706 {
707         u32 *map = (u32 *)tn;
708         u32 bit_in_map;
709         u32 bit_in_word;
710         u32 word_in_map;
711         u32 val;
712
713         pos &= YAFFS_TNODES_LEVEL0_MASK;
714
715         bit_in_map = pos * dev->tnode_width;
716         word_in_map = bit_in_map / 32;
717         bit_in_word = bit_in_map & (32 - 1);
718
719         val = map[word_in_map] >> bit_in_word;
720
721         if      (dev->tnode_width > (32 - bit_in_word)) {
722                 bit_in_word = (32 - bit_in_word);
723                 word_in_map++;;
724                 val |= (map[word_in_map] << bit_in_word);
725         }
726
727         val &= dev->tnode_mask;
728         val <<= dev->chunk_grp_bits;
729
730         return val;
731 }
732
733 /* ------------------- End of individual tnode manipulation -----------------*/
734
735 /* ---------Functions to manipulate the look-up tree (made up of tnodes) ------
736  * The look up tree is represented by the top tnode and the number of top_level
737  * in the tree. 0 means only the level 0 tnode is in the tree.
738  */
739
740 /* FindLevel0Tnode finds the level 0 tnode, if one exists. */
741 struct yaffs_tnode *yaffs_find_tnode_0(struct yaffs_dev *dev,
742                                         struct yaffs_file_var *file_struct,
743                                         u32 chunk_id)
744 {
745         struct yaffs_tnode *tn = file_struct->top;
746         u32 i;
747         int required_depth;
748         int level = file_struct->top_level;
749
750         dev=dev;
751
752         /* Check sane level and chunk Id */
753         if (level < 0 || level > YAFFS_TNODES_MAX_LEVEL)
754                 return NULL;
755
756         if (chunk_id > YAFFS_MAX_CHUNK_ID)
757                 return NULL;
758
759         /* First check we're tall enough (ie enough top_level) */
760
761         i = chunk_id >> YAFFS_TNODES_LEVEL0_BITS;
762         required_depth = 0;
763         while (i) {
764                 i >>= YAFFS_TNODES_INTERNAL_BITS;
765                 required_depth++;
766         }
767
768         if (required_depth > file_struct->top_level)
769                 return NULL; /* Not tall enough, so we can't find it */
770
771         /* Traverse down to level 0 */
772         while (level > 0 && tn) {
773                 tn = tn->internal[(chunk_id >>
774                         (YAFFS_TNODES_LEVEL0_BITS +
775                                 (level - 1) *
776                                 YAFFS_TNODES_INTERNAL_BITS)) &
777                         YAFFS_TNODES_INTERNAL_MASK];
778                 level--;
779         }
780
781         return tn;
782 }
783
784 /* AddOrFindLevel0Tnode finds the level 0 tnode if it exists, otherwise first expands the tree.
785  * This happens in two steps:
786  *  1. If the tree isn't tall enough, then make it taller.
787  *  2. Scan down the tree towards the level 0 tnode adding tnodes if required.
788  *
789  * Used when modifying the tree.
790  *
791  *  If the tn argument is NULL, then a fresh tnode will be added otherwise the specified tn will
792  *  be plugged into the ttree.
793  */
794
795 struct yaffs_tnode *yaffs_add_find_tnode_0(struct yaffs_dev *dev,
796                                         struct yaffs_file_var *file_struct,
797                                         u32 chunk_id,
798                                         struct yaffs_tnode *passed_tn)
799 {
800         int required_depth;
801         int i;
802         int l;
803         struct yaffs_tnode *tn;
804
805         u32 x;
806
807
808         /* Check sane level and page Id */
809         if (file_struct->top_level < 0 || file_struct->top_level > YAFFS_TNODES_MAX_LEVEL)
810                 return NULL;
811
812         if (chunk_id > YAFFS_MAX_CHUNK_ID)
813                 return NULL;
814
815         /* First check we're tall enough (ie enough top_level) */
816
817         x = chunk_id >> YAFFS_TNODES_LEVEL0_BITS;
818         required_depth = 0;
819         while (x) {
820                 x >>= YAFFS_TNODES_INTERNAL_BITS;
821                 required_depth++;
822         }
823
824
825         if (required_depth > file_struct->top_level) {
826                 /* Not tall enough, gotta make the tree taller */
827                 for (i = file_struct->top_level; i < required_depth; i++) {
828
829                         tn = yaffs_get_tnode(dev);
830
831                         if (tn) {
832                                 tn->internal[0] = file_struct->top;
833                                 file_struct->top = tn;
834                                 file_struct->top_level++;
835                         } else {
836                                 T(YAFFS_TRACE_ERROR,
837                                         (TSTR("yaffs: no more tnodes" TENDSTR)));
838                                 return NULL;
839                         }
840                 }
841         }
842
843         /* Traverse down to level 0, adding anything we need */
844
845         l = file_struct->top_level;
846         tn = file_struct->top;
847
848         if (l > 0) {
849                 while (l > 0 && tn) {
850                         x = (chunk_id >>
851                              (YAFFS_TNODES_LEVEL0_BITS +
852                               (l - 1) * YAFFS_TNODES_INTERNAL_BITS)) &
853                             YAFFS_TNODES_INTERNAL_MASK;
854
855
856                         if ((l > 1) && !tn->internal[x]) {
857                                 /* Add missing non-level-zero tnode */
858                                 tn->internal[x] = yaffs_get_tnode(dev);
859                                 if(!tn->internal[x])
860                                         return NULL;
861                         } else if (l == 1) {
862                                 /* Looking from level 1 at level 0 */
863                                 if (passed_tn) {
864                                         /* If we already have one, then release it.*/
865                                         if (tn->internal[x])
866                                                 yaffs_free_tnode(dev, tn->internal[x]);
867                                         tn->internal[x] = passed_tn;
868
869                                 } else if (!tn->internal[x]) {
870                                         /* Don't have one, none passed in */
871                                         tn->internal[x] = yaffs_get_tnode(dev);
872                                         if(!tn->internal[x])
873                                                 return NULL;
874                                 }
875                         }
876
877                         tn = tn->internal[x];
878                         l--;
879                 }
880         } else {
881                 /* top is level 0 */
882                 if (passed_tn) {
883                         memcpy(tn, passed_tn, (dev->tnode_width * YAFFS_NTNODES_LEVEL0)/8);
884                         yaffs_free_tnode(dev, passed_tn);
885                 }
886         }
887
888         return tn;
889 }
890
891 static int yaffs_find_chunk_in_group(struct yaffs_dev *dev, int the_chunk,
892                                 struct yaffs_ext_tags *tags, int obj_id,
893                                 int inode_chunk)
894 {
895         int j;
896
897         for (j = 0; the_chunk && j < dev->chunk_grp_size; j++) {
898                 if (yaffs_check_chunk_bit(dev, the_chunk / dev->param.chunks_per_block,
899                                 the_chunk % dev->param.chunks_per_block)) {
900                         
901                         if(dev->chunk_grp_size == 1)
902                                 return the_chunk;
903                         else {
904                                 yaffs_rd_chunk_tags_nand(dev, the_chunk, NULL,
905                                                                 tags);
906                                 if (yaffs_tags_match(tags, obj_id, inode_chunk)) {
907                                         /* found it; */
908                                         return the_chunk;
909                                 }
910                         }
911                 }
912                 the_chunk++;
913         }
914         return -1;
915 }
916
917
918 static void yaffs_soft_del_chunk(struct yaffs_dev *dev, int chunk)
919 {
920         struct yaffs_block_info *the_block;
921         unsigned block_no;
922
923         T(YAFFS_TRACE_DELETION, (TSTR("soft delete chunk %d" TENDSTR), chunk));
924
925         block_no =  chunk / dev->param.chunks_per_block;
926         the_block = yaffs_get_block_info(dev, block_no);
927         if (the_block) {
928                 the_block->soft_del_pages++;
929                 dev->n_free_chunks++;
930                 yaffs2_update_oldest_dirty_seq(dev, block_no, the_block);
931         }
932 }
933
934 /* SoftDeleteWorker scans backwards through the tnode tree and soft deletes all the chunks in the file.
935  * All soft deleting does is increment the block's softdelete count and pulls the chunk out
936  * of the tnode.
937  * Thus, essentially this is the same as DeleteWorker except that the chunks are soft deleted.
938  */
939
940 static int yaffs_soft_del_worker(struct yaffs_obj *in, struct yaffs_tnode *tn,
941                                   u32 level, int chunk_offset)
942 {
943         int i;
944         int the_chunk;
945         int all_done = 1;
946         struct yaffs_dev *dev = in->my_dev;
947
948         if (tn) {
949                 if (level > 0) {
950
951                         for (i = YAFFS_NTNODES_INTERNAL - 1; all_done && i >= 0;
952                              i--) {
953                                 if (tn->internal[i]) {
954                                         all_done =
955                                             yaffs_soft_del_worker(in,
956                                                                    tn->
957                                                                    internal[i],
958                                                                    level - 1,
959                                                                    (chunk_offset
960                                                                     <<
961                                                                     YAFFS_TNODES_INTERNAL_BITS)
962                                                                    + i);
963                                         if (all_done) {
964                                                 yaffs_free_tnode(dev,
965                                                                 tn->
966                                                                 internal[i]);
967                                                 tn->internal[i] = NULL;
968                                         } else {
969                                                 /* Hoosterman... how could this happen? */
970                                         }
971                                 }
972                         }
973                         return (all_done) ? 1 : 0;
974                 } else if (level == 0) {
975
976                         for (i = YAFFS_NTNODES_LEVEL0 - 1; i >= 0; i--) {
977                                 the_chunk = yaffs_get_group_base(dev, tn, i);
978                                 if (the_chunk) {
979                                         /* Note this does not find the real chunk, only the chunk group.
980                                          * We make an assumption that a chunk group is not larger than
981                                          * a block.
982                                          */
983                                         yaffs_soft_del_chunk(dev, the_chunk);
984                                         yaffs_load_tnode_0(dev, tn, i, 0);
985                                 }
986
987                         }
988                         return 1;
989
990                 }
991
992         }
993
994         return 1;
995
996 }
997
998 static void yaffs_soft_del_file(struct yaffs_obj *obj)
999 {
1000         if (obj->deleted &&
1001             obj->variant_type == YAFFS_OBJECT_TYPE_FILE && !obj->soft_del) {
1002                 if (obj->n_data_chunks <= 0) {
1003                         /* Empty file with no duplicate object headers, just delete it immediately */
1004                         yaffs_free_tnode(obj->my_dev,
1005                                         obj->variant.file_variant.top);
1006                         obj->variant.file_variant.top = NULL;
1007                         T(YAFFS_TRACE_TRACING,
1008                           (TSTR("yaffs: Deleting empty file %d" TENDSTR),
1009                            obj->obj_id));
1010                         yaffs_generic_obj_del(obj);
1011                 } else {
1012                         yaffs_soft_del_worker(obj,
1013                                                obj->variant.file_variant.top,
1014                                                obj->variant.file_variant.
1015                                                top_level, 0);
1016                         obj->soft_del = 1;
1017                 }
1018         }
1019 }
1020
1021 /* Pruning removes any part of the file structure tree that is beyond the
1022  * bounds of the file (ie that does not point to chunks).
1023  *
1024  * A file should only get pruned when its size is reduced.
1025  *
1026  * Before pruning, the chunks must be pulled from the tree and the
1027  * level 0 tnode entries must be zeroed out.
1028  * Could also use this for file deletion, but that's probably better handled
1029  * by a special case.
1030  *
1031  * This function is recursive. For levels > 0 the function is called again on
1032  * any sub-tree. For level == 0 we just check if the sub-tree has data.
1033  * If there is no data in a subtree then it is pruned.
1034  */
1035
1036 static struct yaffs_tnode *yaffs_prune_worker(struct yaffs_dev *dev, struct yaffs_tnode *tn,
1037                                 u32 level, int del0)
1038 {
1039         int i;
1040         int has_data;
1041
1042         if (tn) {
1043                 has_data = 0;
1044
1045                 if(level > 0){
1046                         for (i = 0; i < YAFFS_NTNODES_INTERNAL; i++) {
1047                                 if (tn->internal[i]) {
1048                                         tn->internal[i] =
1049                                                 yaffs_prune_worker(dev, tn->internal[i],
1050                                                         level - 1,
1051                                                         (i == 0) ? del0 : 1);
1052                                 }
1053
1054                                 if (tn->internal[i])
1055                                         has_data++;
1056                         }
1057                 } else {
1058                         int tnode_size_u32 = dev->tnode_size/sizeof(u32);
1059                         u32 *map = (u32 *)tn;
1060
1061                         for(i = 0; !has_data && i < tnode_size_u32; i++){
1062                                 if(map[i])
1063                                         has_data++;
1064                         }
1065                 }
1066
1067                 if (has_data == 0 && del0) {
1068                         /* Free and return NULL */
1069
1070                         yaffs_free_tnode(dev, tn);
1071                         tn = NULL;
1072                 }
1073
1074         }
1075
1076         return tn;
1077
1078 }
1079
1080 static int yaffs_prune_tree(struct yaffs_dev *dev,
1081                                 struct yaffs_file_var *file_struct)
1082 {
1083         int i;
1084         int has_data;
1085         int done = 0;
1086         struct yaffs_tnode *tn;
1087
1088         if (file_struct->top_level > 0) {
1089                 file_struct->top =
1090                     yaffs_prune_worker(dev, file_struct->top, file_struct->top_level, 0);
1091
1092                 /* Now we have a tree with all the non-zero branches NULL but the height
1093                  * is the same as it was.
1094                  * Let's see if we can trim internal tnodes to shorten the tree.
1095                  * We can do this if only the 0th element in the tnode is in use
1096                  * (ie all the non-zero are NULL)
1097                  */
1098
1099                 while (file_struct->top_level && !done) {
1100                         tn = file_struct->top;
1101
1102                         has_data = 0;
1103                         for (i = 1; i < YAFFS_NTNODES_INTERNAL; i++) {
1104                                 if (tn->internal[i])
1105                                         has_data++;
1106                         }
1107
1108                         if (!has_data) {
1109                                 file_struct->top = tn->internal[0];
1110                                 file_struct->top_level--;
1111                                 yaffs_free_tnode(dev, tn);
1112                         } else {
1113                                 done = 1;
1114                         }
1115                 }
1116         }
1117
1118         return YAFFS_OK;
1119 }
1120
1121 /*-------------------- End of File Structure functions.-------------------*/
1122
1123
1124 /* AllocateEmptyObject gets us a clean Object. Tries to make allocate more if we run out */
1125 static struct yaffs_obj *yaffs_alloc_empty_obj(struct yaffs_dev *dev)
1126 {
1127         struct yaffs_obj *obj = yaffs_alloc_raw_obj(dev);
1128
1129         if (obj) {
1130                 dev->n_obj++;
1131
1132                 /* Now sweeten it up... */
1133
1134                 memset(obj, 0, sizeof(struct yaffs_obj));
1135                 obj->being_created = 1;
1136
1137                 obj->my_dev = dev;
1138                 obj->hdr_chunk = 0;
1139                 obj->variant_type = YAFFS_OBJECT_TYPE_UNKNOWN;
1140                 INIT_LIST_HEAD(&(obj->hard_links));
1141                 INIT_LIST_HEAD(&(obj->hash_link));
1142                 INIT_LIST_HEAD(&obj->siblings);
1143
1144
1145                 /* Now make the directory sane */
1146                 if (dev->root_dir) {
1147                         obj->parent = dev->root_dir;
1148                         list_add(&(obj->siblings), &dev->root_dir->variant.dir_variant.children);
1149                 }
1150
1151                 /* Add it to the lost and found directory.
1152                  * NB Can't put root or lost-n-found in lost-n-found so
1153                  * check if lost-n-found exists first
1154                  */
1155                 if (dev->lost_n_found)
1156                         yaffs_add_obj_to_dir(dev->lost_n_found, obj);
1157
1158                 obj->being_created = 0;
1159         }
1160
1161         dev->checkpoint_blocks_required = 0; /* force recalculation*/
1162
1163         return obj;
1164 }
1165
1166 static struct yaffs_obj *yaffs_create_fake_dir(struct yaffs_dev *dev, int number,
1167                                                u32 mode)
1168 {
1169
1170         struct yaffs_obj *obj =
1171             yaffs_new_obj(dev, number, YAFFS_OBJECT_TYPE_DIRECTORY);
1172         if (obj) {
1173                 obj->fake = 1;          /* it is fake so it might have no NAND presence... */
1174                 obj->rename_allowed = 0;        /* ... and we're not allowed to rename it... */
1175                 obj->unlink_allowed = 0;        /* ... or unlink it */
1176                 obj->deleted = 0;
1177                 obj->unlinked = 0;
1178                 obj->yst_mode = mode;
1179                 obj->my_dev = dev;
1180                 obj->hdr_chunk = 0;     /* Not a valid chunk. */
1181         }
1182
1183         return obj;
1184
1185 }
1186
1187 static void yaffs_unhash_obj(struct yaffs_obj *obj)
1188 {
1189         int bucket;
1190         struct yaffs_dev *dev = obj->my_dev;
1191
1192         /* If it is still linked into the bucket list, free from the list */
1193         if (!list_empty(&obj->hash_link)) {
1194                 list_del_init(&obj->hash_link);
1195                 bucket = yaffs_hash_fn(obj->obj_id);
1196                 dev->obj_bucket[bucket].count--;
1197         }
1198 }
1199
1200 /*  FreeObject frees up a Object and puts it back on the free list */
1201 static void yaffs_free_obj(struct yaffs_obj *obj)
1202 {
1203         struct yaffs_dev *dev = obj->my_dev;
1204
1205         T(YAFFS_TRACE_OS, (TSTR("FreeObject %p inode %p"TENDSTR), obj, obj->my_inode));
1206
1207         if (!obj)
1208                 YBUG();
1209         if (obj->parent)
1210                 YBUG();
1211         if (!list_empty(&obj->siblings))
1212                 YBUG();
1213
1214
1215         if (obj->my_inode) {
1216                 /* We're still hooked up to a cached inode.
1217                  * Don't delete now, but mark for later deletion
1218                  */
1219                 obj->defered_free = 1;
1220                 return;
1221         }
1222
1223         yaffs_unhash_obj(obj);
1224
1225         yaffs_free_raw_obj(dev,obj);
1226         dev->n_obj--;
1227         dev->checkpoint_blocks_required = 0; /* force recalculation*/
1228 }
1229
1230
1231 void yaffs_handle_defered_free(struct yaffs_obj *obj)
1232 {
1233         if (obj->defered_free)
1234                 yaffs_free_obj(obj);
1235 }
1236
1237 static void yaffs_init_tnodes_and_objs(struct yaffs_dev *dev)
1238 {
1239         int i;
1240
1241         dev->n_obj = 0;
1242         dev->n_tnodes = 0;
1243
1244         yaffs_init_raw_tnodes_and_objs(dev);
1245
1246         for (i = 0; i < YAFFS_NOBJECT_BUCKETS; i++) {
1247                 INIT_LIST_HEAD(&dev->obj_bucket[i].list);
1248                 dev->obj_bucket[i].count = 0;
1249         }
1250 }
1251
1252 static int yaffs_find_nice_bucket(struct yaffs_dev *dev)
1253 {
1254         int i;
1255         int l = 999;
1256         int lowest = 999999;
1257
1258
1259         /* Search for the shortest list or one that
1260          * isn't too long.
1261          */
1262
1263         for (i = 0; i < 10 && lowest > 4; i++) {
1264                 dev->bucket_finder++;
1265                 dev->bucket_finder %= YAFFS_NOBJECT_BUCKETS;
1266                 if (dev->obj_bucket[dev->bucket_finder].count < lowest) {
1267                         lowest = dev->obj_bucket[dev->bucket_finder].count;
1268                         l = dev->bucket_finder;
1269                 }
1270
1271         }
1272
1273         return l;
1274 }
1275
1276 static int yaffs_new_obj_id(struct yaffs_dev *dev)
1277 {
1278         int bucket = yaffs_find_nice_bucket(dev);
1279
1280         /* Now find an object value that has not already been taken
1281          * by scanning the list.
1282          */
1283
1284         int found = 0;
1285         struct list_head *i;
1286
1287         u32 n = (u32) bucket;
1288
1289         /* yaffs_check_obj_hash_sane();  */
1290
1291         while (!found) {
1292                 found = 1;
1293                 n += YAFFS_NOBJECT_BUCKETS;
1294                 if (1 || dev->obj_bucket[bucket].count > 0) {
1295                         list_for_each(i, &dev->obj_bucket[bucket].list) {
1296                                 /* If there is already one in the list */
1297                                 if (i && list_entry(i, struct yaffs_obj,
1298                                                 hash_link)->obj_id == n) {
1299                                         found = 0;
1300                                 }
1301                         }
1302                 }
1303         }
1304
1305         return n;
1306 }
1307
1308 static void yaffs_hash_obj(struct yaffs_obj *in)
1309 {
1310         int bucket = yaffs_hash_fn(in->obj_id);
1311         struct yaffs_dev *dev = in->my_dev;
1312
1313         list_add(&in->hash_link, &dev->obj_bucket[bucket].list);
1314         dev->obj_bucket[bucket].count++;
1315 }
1316
1317 struct yaffs_obj *yaffs_find_by_number(struct yaffs_dev *dev, u32 number)
1318 {
1319         int bucket = yaffs_hash_fn(number);
1320         struct list_head *i;
1321         struct yaffs_obj *in;
1322
1323         list_for_each(i, &dev->obj_bucket[bucket].list) {
1324                 /* Look if it is in the list */
1325                 if (i) {
1326                         in = list_entry(i, struct yaffs_obj, hash_link);
1327                         if (in->obj_id == number) {
1328
1329                                 /* Don't tell the VFS about this one if it is defered free */
1330                                 if (in->defered_free)
1331                                         return NULL;
1332
1333                                 return in;
1334                         }
1335                 }
1336         }
1337
1338         return NULL;
1339 }
1340
1341 struct yaffs_obj *yaffs_new_obj(struct yaffs_dev *dev, int number,
1342                                     enum yaffs_obj_type type)
1343 {
1344         struct yaffs_obj *the_obj=NULL;
1345         struct yaffs_tnode *tn = NULL;
1346
1347         if (number < 0)
1348                 number = yaffs_new_obj_id(dev);
1349
1350         if (type == YAFFS_OBJECT_TYPE_FILE) {
1351                 tn = yaffs_get_tnode(dev);
1352                 if (!tn)
1353                         return NULL;
1354         }
1355
1356         the_obj = yaffs_alloc_empty_obj(dev);
1357         if (!the_obj){
1358                 if(tn)
1359                         yaffs_free_tnode(dev,tn);
1360                 return NULL;
1361         }
1362
1363
1364         if (the_obj) {
1365                 the_obj->fake = 0;
1366                 the_obj->rename_allowed = 1;
1367                 the_obj->unlink_allowed = 1;
1368                 the_obj->obj_id = number;
1369                 yaffs_hash_obj(the_obj);
1370                 the_obj->variant_type = type;
1371                 yaffs_load_current_time(the_obj,1,1);
1372
1373                 switch (type) {
1374                 case YAFFS_OBJECT_TYPE_FILE:
1375                         the_obj->variant.file_variant.file_size = 0;
1376                         the_obj->variant.file_variant.scanned_size = 0;
1377                         the_obj->variant.file_variant.shrink_size = ~0;/* max */
1378                         the_obj->variant.file_variant.top_level = 0;
1379                         the_obj->variant.file_variant.top = tn;
1380                         break;
1381                 case YAFFS_OBJECT_TYPE_DIRECTORY:
1382                         INIT_LIST_HEAD(&the_obj->variant.dir_variant.
1383                                         children);
1384                         INIT_LIST_HEAD(&the_obj->variant.dir_variant.
1385                                         dirty);
1386                         break;
1387                 case YAFFS_OBJECT_TYPE_SYMLINK:
1388                 case YAFFS_OBJECT_TYPE_HARDLINK:
1389                 case YAFFS_OBJECT_TYPE_SPECIAL:
1390                         /* No action required */
1391                         break;
1392                 case YAFFS_OBJECT_TYPE_UNKNOWN:
1393                         /* todo this should not happen */
1394                         break;
1395                 }
1396         }
1397
1398         return the_obj;
1399 }
1400
1401 struct yaffs_obj *yaffs_find_or_create_by_number(struct yaffs_dev *dev,
1402                                                 int number,
1403                                                 enum yaffs_obj_type type)
1404 {
1405         struct yaffs_obj *the_obj = NULL;
1406
1407         if (number > 0)
1408                 the_obj = yaffs_find_by_number(dev, number);
1409
1410         if (!the_obj)
1411                 the_obj = yaffs_new_obj(dev, number, type);
1412
1413         return the_obj;
1414
1415 }
1416
1417
1418 YCHAR *yaffs_clone_str(const YCHAR *str)
1419 {
1420         YCHAR *new_str = NULL;
1421         int len;
1422
1423         if (!str)
1424                 str = _Y("");
1425
1426         len = yaffs_strnlen(str,YAFFS_MAX_ALIAS_LENGTH);
1427         new_str = YMALLOC((len + 1) * sizeof(YCHAR));
1428         if (new_str){
1429                 yaffs_strncpy(new_str, str,len);
1430                 new_str[len] = 0;
1431         }
1432         return new_str;
1433
1434 }
1435
1436 /*
1437  * Mknod (create) a new object.
1438  * equiv_obj only has meaning for a hard link;
1439  * alias_str only has meaning for a symlink.
1440  * rdev only has meaning for devices (a subset of special objects)
1441  */
1442
1443 static struct yaffs_obj *yaffs_create_obj(enum yaffs_obj_type type,
1444                                        struct yaffs_obj *parent,
1445                                        const YCHAR *name,
1446                                        u32 mode,
1447                                        u32 uid,
1448                                        u32 gid,
1449                                        struct yaffs_obj *equiv_obj,
1450                                        const YCHAR *alias_str, u32 rdev)
1451 {
1452         struct yaffs_obj *in;
1453         YCHAR *str = NULL;
1454
1455         struct yaffs_dev *dev = parent->my_dev;
1456
1457         /* Check if the entry exists. If it does then fail the call since we don't want a dup.*/
1458         if (yaffs_find_by_name(parent, name))
1459                 return NULL;
1460
1461         if (type == YAFFS_OBJECT_TYPE_SYMLINK) {
1462                 str = yaffs_clone_str(alias_str);
1463                 if (!str)
1464                         return NULL;
1465         }
1466
1467         in = yaffs_new_obj(dev, -1, type);
1468
1469         if (!in){
1470                 if(str)
1471                         YFREE(str);
1472                 return NULL;
1473         }
1474
1475
1476
1477
1478
1479         if (in) {
1480                 in->hdr_chunk = 0;
1481                 in->valid = 1;
1482                 in->variant_type = type;
1483
1484                 in->yst_mode = mode;
1485
1486                 yaffs_attribs_init(in, gid, uid, rdev);
1487
1488                 in->n_data_chunks = 0;
1489
1490                 yaffs_set_obj_name(in, name);
1491                 in->dirty = 1;
1492
1493                 yaffs_add_obj_to_dir(parent, in);
1494
1495                 in->my_dev = parent->my_dev;
1496
1497                 switch (type) {
1498                 case YAFFS_OBJECT_TYPE_SYMLINK:
1499                         in->variant.symlink_variant.alias = str;
1500                         break;
1501                 case YAFFS_OBJECT_TYPE_HARDLINK:
1502                         in->variant.hardlink_variant.equiv_obj =
1503                                 equiv_obj;
1504                         in->variant.hardlink_variant.equiv_id =
1505                                 equiv_obj->obj_id;
1506                         list_add(&in->hard_links, &equiv_obj->hard_links);
1507                         break;
1508                 case YAFFS_OBJECT_TYPE_FILE:
1509                 case YAFFS_OBJECT_TYPE_DIRECTORY:
1510                 case YAFFS_OBJECT_TYPE_SPECIAL:
1511                 case YAFFS_OBJECT_TYPE_UNKNOWN:
1512                         /* do nothing */
1513                         break;
1514                 }
1515
1516                 if (yaffs_update_oh(in, name, 0, 0, 0, NULL) < 0) {
1517                         /* Could not create the object header, fail the creation */
1518                         yaffs_del_obj(in);
1519                         in = NULL;
1520                 }
1521
1522                 yaffs_update_parent(parent);
1523         }
1524
1525         return in;
1526 }
1527
1528 struct yaffs_obj *yaffs_create_file(struct yaffs_obj *parent, const YCHAR *name,
1529                         u32 mode, u32 uid, u32 gid)
1530 {
1531         return yaffs_create_obj(YAFFS_OBJECT_TYPE_FILE, parent, name, mode,
1532                                 uid, gid, NULL, NULL, 0);
1533 }
1534
1535 struct yaffs_obj *yaffs_create_dir(struct yaffs_obj *parent, const YCHAR *name,
1536                                 u32 mode, u32 uid, u32 gid)
1537 {
1538         return yaffs_create_obj(YAFFS_OBJECT_TYPE_DIRECTORY, parent, name,
1539                                  mode, uid, gid, NULL, NULL, 0);
1540 }
1541
1542 struct yaffs_obj *yaffs_create_special(struct yaffs_obj *parent, const YCHAR *name,
1543                                 u32 mode, u32 uid, u32 gid, u32 rdev)
1544 {
1545         return yaffs_create_obj(YAFFS_OBJECT_TYPE_SPECIAL, parent, name, mode,
1546                                  uid, gid, NULL, NULL, rdev);
1547 }
1548
1549 struct yaffs_obj *yaffs_create_symlink(struct yaffs_obj *parent, const YCHAR *name,
1550                                 u32 mode, u32 uid, u32 gid,
1551                                 const YCHAR *alias)
1552 {
1553         return yaffs_create_obj(YAFFS_OBJECT_TYPE_SYMLINK, parent, name, mode,
1554                                 uid, gid, NULL, alias, 0);
1555 }
1556
1557 /* yaffs_link_obj returns the object id of the equivalent object.*/
1558 struct yaffs_obj *yaffs_link_obj(struct yaffs_obj *parent, const YCHAR *name,
1559                         struct yaffs_obj *equiv_obj)
1560 {
1561         /* Get the real object in case we were fed a hard link as an equivalent object */
1562         equiv_obj = yaffs_get_equivalent_obj(equiv_obj);
1563
1564         if (yaffs_create_obj
1565             (YAFFS_OBJECT_TYPE_HARDLINK, parent, name, 0, 0, 0,
1566              equiv_obj, NULL, 0)) {
1567                 return equiv_obj;
1568         } else {
1569                 return NULL;
1570         }
1571
1572 }
1573
1574 static int yaffs_change_obj_name(struct yaffs_obj *obj, struct yaffs_obj *new_dir,
1575                                 const YCHAR *new_name, int force, int shadows)
1576 {
1577         int unlink_op;
1578         int del_op;
1579
1580         struct yaffs_obj *existing_target;
1581
1582         if (new_dir == NULL)
1583                 new_dir = obj->parent;  /* use the old directory */
1584
1585         if (new_dir->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY) {
1586                 T(YAFFS_TRACE_ALWAYS,
1587                   (TSTR
1588                    ("tragedy: yaffs_change_obj_name: new_dir is not a directory"
1589                     TENDSTR)));
1590                 YBUG();
1591         }
1592
1593         /* TODO: Do we need this different handling for YAFFS2 and YAFFS1?? */
1594         if (obj->my_dev->param.is_yaffs2)
1595                 unlink_op = (new_dir == obj->my_dev->unlinked_dir);
1596         else
1597                 unlink_op = (new_dir == obj->my_dev->unlinked_dir
1598                             && obj->variant_type == YAFFS_OBJECT_TYPE_FILE);
1599
1600         del_op = (new_dir == obj->my_dev->del_dir);
1601
1602         existing_target = yaffs_find_by_name(new_dir, new_name);
1603
1604         /* If the object is a file going into the unlinked directory,
1605          *   then it is OK to just stuff it in since duplicate names are allowed.
1606          *   else only proceed if the new name does not exist and if we're putting
1607          *   it into a directory.
1608          */
1609         if ((unlink_op ||
1610              del_op ||
1611              force ||
1612              (shadows > 0) ||
1613              !existing_target) &&
1614             new_dir->variant_type == YAFFS_OBJECT_TYPE_DIRECTORY) {
1615                 yaffs_set_obj_name(obj, new_name);
1616                 obj->dirty = 1;
1617
1618                 yaffs_add_obj_to_dir(new_dir, obj);
1619
1620                 if (unlink_op)
1621                         obj->unlinked = 1;
1622
1623                 /* If it is a deletion then we mark it as a shrink for gc purposes. */
1624                 if (yaffs_update_oh(obj, new_name, 0, del_op, shadows, NULL) >= 0)
1625                         return YAFFS_OK;
1626         }
1627
1628         return YAFFS_FAIL;
1629 }
1630
1631 int yaffs_rename_obj(struct yaffs_obj *old_dir, const YCHAR *old_name,
1632                 struct yaffs_obj *new_dir, const YCHAR *new_name)
1633 {
1634         struct yaffs_obj *obj = NULL;
1635         struct yaffs_obj *existing_target = NULL;
1636         int force = 0;
1637         int result;
1638         struct yaffs_dev *dev;
1639
1640
1641         if (!old_dir || old_dir->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY)
1642                 YBUG();
1643         if (!new_dir || new_dir->variant_type != YAFFS_OBJECT_TYPE_DIRECTORY)
1644                 YBUG();
1645
1646         dev = old_dir->my_dev;
1647
1648 #ifdef CONFIG_YAFFS_CASE_INSENSITIVE
1649         /* Special case for case insemsitive systems.
1650          * While look-up is case insensitive, the name isn't.
1651          * Therefore we might want to change x.txt to X.txt
1652         */
1653         if (old_dir == new_dir && yaffs_strcmp(old_name, new_name) == 0)
1654                 force = 1;
1655 #endif
1656
1657         if(yaffs_strnlen(new_name,YAFFS_MAX_NAME_LENGTH+1) > YAFFS_MAX_NAME_LENGTH)
1658                 /* ENAMETOOLONG */
1659                 return YAFFS_FAIL;
1660
1661         obj = yaffs_find_by_name(old_dir, old_name);
1662
1663         if (obj && obj->rename_allowed) {
1664
1665                 /* Now do the handling for an existing target, if there is one */
1666
1667                 existing_target = yaffs_find_by_name(new_dir, new_name);
1668                 if (existing_target &&
1669                         existing_target->variant_type == YAFFS_OBJECT_TYPE_DIRECTORY &&
1670                         !list_empty(&existing_target->variant.dir_variant.children)) {
1671                         /* There is a target that is a non-empty directory, so we fail */
1672                         return YAFFS_FAIL;      /* EEXIST or ENOTEMPTY */
1673                 } else if (existing_target && existing_target != obj) {
1674                         /* Nuke the target first, using shadowing,
1675                          * but only if it isn't the same object.
1676                          *
1677                          * Note we must disable gc otherwise it can mess up the shadowing.
1678                          *
1679                          */
1680                         dev->gc_disable=1;
1681                         yaffs_change_obj_name(obj, new_dir, new_name, force,
1682                                                 existing_target->obj_id);
1683                         existing_target->is_shadowed = 1;
1684                         yaffs_unlink_obj(existing_target);
1685                         dev->gc_disable=0;
1686                 }
1687
1688                 result = yaffs_change_obj_name(obj, new_dir, new_name, 1, 0);
1689
1690                 yaffs_update_parent(old_dir);
1691                 if(new_dir != old_dir)
1692                         yaffs_update_parent(new_dir);
1693                 
1694                 return result;
1695         }
1696         return YAFFS_FAIL;
1697 }
1698
1699 /*------------------------- Block Management and Page Allocation ----------------*/
1700
1701 static int yaffs_init_blocks(struct yaffs_dev *dev)
1702 {
1703         int n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
1704
1705         dev->block_info = NULL;
1706         dev->chunk_bits = NULL;
1707
1708         dev->alloc_block = -1;  /* force it to get a new one */
1709
1710         /* If the first allocation strategy fails, thry the alternate one */
1711         dev->block_info = YMALLOC(n_blocks * sizeof(struct yaffs_block_info));
1712         if (!dev->block_info) {
1713                 dev->block_info = YMALLOC_ALT(n_blocks * sizeof(struct yaffs_block_info));
1714                 dev->block_info_alt = 1;
1715         } else
1716                 dev->block_info_alt = 0;
1717
1718         if (dev->block_info) {
1719                 /* Set up dynamic blockinfo stuff. */
1720                 dev->chunk_bit_stride = (dev->param.chunks_per_block + 7) / 8; /* round up bytes */
1721                 dev->chunk_bits = YMALLOC(dev->chunk_bit_stride * n_blocks);
1722                 if (!dev->chunk_bits) {
1723                         dev->chunk_bits = YMALLOC_ALT(dev->chunk_bit_stride * n_blocks);
1724                         dev->chunk_bits_alt = 1;
1725                 } else
1726                         dev->chunk_bits_alt = 0;
1727         }
1728
1729         if (dev->block_info && dev->chunk_bits) {
1730                 memset(dev->block_info, 0, n_blocks * sizeof(struct yaffs_block_info));
1731                 memset(dev->chunk_bits, 0, dev->chunk_bit_stride * n_blocks);
1732                 return YAFFS_OK;
1733         }
1734
1735         return YAFFS_FAIL;
1736 }
1737
1738 static void yaffs_deinit_blocks(struct yaffs_dev *dev)
1739 {
1740         if (dev->block_info_alt && dev->block_info)
1741                 YFREE_ALT(dev->block_info);
1742         else if (dev->block_info)
1743                 YFREE(dev->block_info);
1744
1745         dev->block_info_alt = 0;
1746
1747         dev->block_info = NULL;
1748
1749         if (dev->chunk_bits_alt && dev->chunk_bits)
1750                 YFREE_ALT(dev->chunk_bits);
1751         else if (dev->chunk_bits)
1752                 YFREE(dev->chunk_bits);
1753         dev->chunk_bits_alt = 0;
1754         dev->chunk_bits = NULL;
1755 }
1756
1757 void yaffs_block_became_dirty(struct yaffs_dev *dev, int block_no)
1758 {
1759         struct yaffs_block_info *bi = yaffs_get_block_info(dev, block_no);
1760
1761         int erased_ok = 0;
1762
1763         /* If the block is still healthy erase it and mark as clean.
1764          * If the block has had a data failure, then retire it.
1765          */
1766
1767         T(YAFFS_TRACE_GC | YAFFS_TRACE_ERASE,
1768                 (TSTR("yaffs_block_became_dirty block %d state %d %s"TENDSTR),
1769                 block_no, bi->block_state, (bi->needs_retiring) ? "needs retiring" : ""));
1770
1771         yaffs2_clear_oldest_dirty_seq(dev,bi);
1772
1773         bi->block_state = YAFFS_BLOCK_STATE_DIRTY;
1774
1775         /* If this is the block being garbage collected then stop gc'ing this block */
1776         if(block_no == dev->gc_block)
1777                 dev->gc_block = 0;
1778
1779         /* If this block is currently the best candidate for gc then drop as a candidate */
1780         if(block_no == dev->gc_dirtiest){
1781                 dev->gc_dirtiest = 0;
1782                 dev->gc_pages_in_use = 0;
1783         }
1784
1785         if (!bi->needs_retiring) {
1786                 yaffs2_checkpt_invalidate(dev);
1787                 erased_ok = yaffs_erase_block(dev, block_no);
1788                 if (!erased_ok) {
1789                         dev->n_erase_failures++;
1790                         T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
1791                           (TSTR("**>> Erasure failed %d" TENDSTR), block_no));
1792                 }
1793         }
1794
1795         if (erased_ok &&
1796             ((yaffs_trace_mask & YAFFS_TRACE_ERASE) || !yaffs_skip_verification(dev))) {
1797                 int i;
1798                 for (i = 0; i < dev->param.chunks_per_block; i++) {
1799                         if (!yaffs_check_chunk_erased
1800                             (dev, block_no * dev->param.chunks_per_block + i)) {
1801                                 T(YAFFS_TRACE_ERROR,
1802                                   (TSTR
1803                                    (">>Block %d erasure supposedly OK, but chunk %d not erased"
1804                                     TENDSTR), block_no, i));
1805                         }
1806                 }
1807         }
1808
1809         if (erased_ok) {
1810                 /* Clean it up... */
1811                 bi->block_state = YAFFS_BLOCK_STATE_EMPTY;
1812                 bi->seq_number = 0;
1813                 dev->n_erased_blocks++;
1814                 bi->pages_in_use = 0;
1815                 bi->soft_del_pages = 0;
1816                 bi->has_shrink_hdr = 0;
1817                 bi->skip_erased_check = 1;  /* This is clean, so no need to check */
1818                 bi->gc_prioritise = 0;
1819                 yaffs_clear_chunk_bits(dev, block_no);
1820
1821                 T(YAFFS_TRACE_ERASE,
1822                   (TSTR("Erased block %d" TENDSTR), block_no));
1823         } else {
1824                 dev->n_free_chunks -= dev->param.chunks_per_block;      /* We lost a block of free space */
1825
1826                 yaffs_retire_block(dev, block_no);
1827                 T(YAFFS_TRACE_ERROR | YAFFS_TRACE_BAD_BLOCKS,
1828                   (TSTR("**>> Block %d retired" TENDSTR), block_no));
1829         }
1830 }
1831
1832 static int yaffs_find_alloc_block(struct yaffs_dev *dev)
1833 {
1834         int i;
1835
1836         struct yaffs_block_info *bi;
1837
1838         if (dev->n_erased_blocks < 1) {
1839                 /* Hoosterman we've got a problem.
1840                  * Can't get space to gc
1841                  */
1842                 T(YAFFS_TRACE_ERROR,
1843                   (TSTR("yaffs tragedy: no more erased blocks" TENDSTR)));
1844
1845                 return -1;
1846         }
1847
1848         /* Find an empty block. */
1849
1850         for (i = dev->internal_start_block; i <= dev->internal_end_block; i++) {
1851                 dev->alloc_block_finder++;
1852                 if (dev->alloc_block_finder < dev->internal_start_block
1853                     || dev->alloc_block_finder > dev->internal_end_block) {
1854                         dev->alloc_block_finder = dev->internal_start_block;
1855                 }
1856
1857                 bi = yaffs_get_block_info(dev, dev->alloc_block_finder);
1858
1859                 if (bi->block_state == YAFFS_BLOCK_STATE_EMPTY) {
1860                         bi->block_state = YAFFS_BLOCK_STATE_ALLOCATING;
1861                         dev->seq_number++;
1862                         bi->seq_number = dev->seq_number;
1863                         dev->n_erased_blocks--;
1864                         T(YAFFS_TRACE_ALLOCATE,
1865                           (TSTR("Allocated block %d, seq  %d, %d left" TENDSTR),
1866                            dev->alloc_block_finder, dev->seq_number,
1867                            dev->n_erased_blocks));
1868                         return dev->alloc_block_finder;
1869                 }
1870         }
1871
1872         T(YAFFS_TRACE_ALWAYS,
1873           (TSTR
1874            ("yaffs tragedy: no more erased blocks, but there should have been %d"
1875             TENDSTR), dev->n_erased_blocks));
1876
1877         return -1;
1878 }
1879
1880
1881 /*
1882  * Check if there's space to allocate...
1883  * Thinks.... do we need top make this ths same as yaffs_get_free_chunks()?
1884  */
1885 int yaffs_check_alloc_available(struct yaffs_dev *dev, int n_chunks)
1886 {
1887         int reserved_chunks;
1888         int reserved_blocks = dev->param.n_reserved_blocks;
1889         int checkpt_blocks;
1890
1891         checkpt_blocks = yaffs_calc_checkpt_blocks_required(dev);
1892
1893         reserved_chunks = ((reserved_blocks + checkpt_blocks) * dev->param.chunks_per_block);
1894
1895         return (dev->n_free_chunks > (reserved_chunks + n_chunks));
1896 }
1897
1898 static int yaffs_alloc_chunk(struct yaffs_dev *dev, int use_reserver,
1899                 struct yaffs_block_info **block_ptr)
1900 {
1901         int ret_val;
1902         struct yaffs_block_info *bi;
1903
1904         if (dev->alloc_block < 0) {
1905                 /* Get next block to allocate off */
1906                 dev->alloc_block = yaffs_find_alloc_block(dev);
1907                 dev->alloc_page = 0;
1908         }
1909
1910         if (!use_reserver && !yaffs_check_alloc_available(dev, 1)) {
1911                 /* Not enough space to allocate unless we're allowed to use the reserve. */
1912                 return -1;
1913         }
1914
1915         if (dev->n_erased_blocks < dev->param.n_reserved_blocks
1916                         && dev->alloc_page == 0) {
1917                 T(YAFFS_TRACE_ALLOCATE, (TSTR("Allocating reserve" TENDSTR)));
1918         }
1919
1920         /* Next page please.... */
1921         if (dev->alloc_block >= 0) {
1922                 bi = yaffs_get_block_info(dev, dev->alloc_block);
1923
1924                 ret_val = (dev->alloc_block * dev->param.chunks_per_block) +
1925                         dev->alloc_page;
1926                 bi->pages_in_use++;
1927                 yaffs_set_chunk_bit(dev, dev->alloc_block,
1928                                 dev->alloc_page);
1929
1930                 dev->alloc_page++;
1931
1932                 dev->n_free_chunks--;
1933
1934                 /* If the block is full set the state to full */
1935                 if (dev->alloc_page >= dev->param.chunks_per_block) {
1936                         bi->block_state = YAFFS_BLOCK_STATE_FULL;
1937                         dev->alloc_block = -1;
1938                 }
1939
1940                 if (block_ptr)
1941                         *block_ptr = bi;
1942
1943                 return ret_val;
1944         }
1945
1946         T(YAFFS_TRACE_ERROR,
1947                         (TSTR("!!!!!!!!! Allocator out !!!!!!!!!!!!!!!!!" TENDSTR)));
1948
1949         return -1;
1950 }
1951
1952 static int yaffs_get_erased_chunks(struct yaffs_dev *dev)
1953 {
1954         int n;
1955
1956         n = dev->n_erased_blocks * dev->param.chunks_per_block;
1957
1958         if (dev->alloc_block > 0)
1959                 n += (dev->param.chunks_per_block - dev->alloc_page);
1960
1961         return n;
1962
1963 }
1964
1965 /*
1966  * yaffs_skip_rest_of_block() skips over the rest of the allocation block
1967  * if we don't want to write to it.
1968  */
1969 void yaffs_skip_rest_of_block(struct yaffs_dev *dev)
1970 {
1971         if(dev->alloc_block > 0){
1972                 struct yaffs_block_info *bi = yaffs_get_block_info(dev, dev->alloc_block);
1973                 if(bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING){
1974                         bi->block_state = YAFFS_BLOCK_STATE_FULL;
1975                         dev->alloc_block = -1;
1976                 }
1977         }
1978 }
1979
1980
1981 static int yaffs_gc_block(struct yaffs_dev *dev, int block,
1982                 int whole_block)
1983 {
1984         int old_chunk;
1985         int new_chunk;
1986         int mark_flash;
1987         int ret_val = YAFFS_OK;
1988         int i;
1989         int is_checkpt_block;
1990         int matching_chunk;
1991         int max_copies;
1992
1993         int chunks_before = yaffs_get_erased_chunks(dev);
1994         int chunks_after;
1995
1996         struct yaffs_ext_tags tags;
1997
1998         struct yaffs_block_info *bi = yaffs_get_block_info(dev, block);
1999
2000         struct yaffs_obj *object;
2001
2002         is_checkpt_block = (bi->block_state == YAFFS_BLOCK_STATE_CHECKPOINT);
2003
2004
2005         T(YAFFS_TRACE_TRACING,
2006                         (TSTR("Collecting block %d, in use %d, shrink %d, whole_block %d" TENDSTR),
2007                          block,
2008                          bi->pages_in_use,
2009                          bi->has_shrink_hdr,
2010                          whole_block));
2011
2012         /*yaffs_verify_free_chunks(dev); */
2013
2014         if(bi->block_state == YAFFS_BLOCK_STATE_FULL)
2015                 bi->block_state = YAFFS_BLOCK_STATE_COLLECTING;
2016         
2017         bi->has_shrink_hdr = 0; /* clear the flag so that the block can erase */
2018
2019         dev->gc_disable = 1;
2020
2021         if (is_checkpt_block ||
2022                         !yaffs_still_some_chunks(dev, block)) {
2023                 T(YAFFS_TRACE_TRACING,
2024                                 (TSTR
2025                                  ("Collecting block %d that has no chunks in use" TENDSTR),
2026                                  block));
2027                 yaffs_block_became_dirty(dev, block);
2028         } else {
2029
2030                 u8 *buffer = yaffs_get_temp_buffer(dev, __LINE__);
2031
2032                 yaffs_verify_blk(dev, bi, block);
2033
2034                 max_copies = (whole_block) ? dev->param.chunks_per_block : 5;
2035                 old_chunk = block * dev->param.chunks_per_block + dev->gc_chunk;
2036
2037                 for (/* init already done */;
2038                      ret_val == YAFFS_OK &&
2039                      dev->gc_chunk < dev->param.chunks_per_block &&
2040                      (bi->block_state == YAFFS_BLOCK_STATE_COLLECTING) &&
2041                      max_copies > 0;
2042                      dev->gc_chunk++, old_chunk++) {
2043                         if (yaffs_check_chunk_bit(dev, block, dev->gc_chunk)) {
2044
2045                                 /* This page is in use and might need to be copied off */
2046
2047                                 max_copies--;
2048
2049                                 mark_flash = 1;
2050
2051                                 yaffs_init_tags(&tags);
2052
2053                                 yaffs_rd_chunk_tags_nand(dev, old_chunk,
2054                                                                 buffer, &tags);
2055
2056                                 object =
2057                                     yaffs_find_by_number(dev,
2058                                                              tags.obj_id);
2059
2060                                 T(YAFFS_TRACE_GC_DETAIL,
2061                                   (TSTR
2062                                    ("Collecting chunk in block %d, %d %d %d " TENDSTR),
2063                                    dev->gc_chunk, tags.obj_id, tags.chunk_id,
2064                                    tags.n_bytes));
2065
2066                                 if (object && !yaffs_skip_verification(dev)) {
2067                                         if (tags.chunk_id == 0)
2068                                                 matching_chunk = object->hdr_chunk;
2069                                         else if (object->soft_del)
2070                                                 matching_chunk = old_chunk; /* Defeat the test */
2071                                         else
2072                                                 matching_chunk = yaffs_find_chunk_in_file(object, tags.chunk_id, NULL);
2073
2074                                         if (old_chunk != matching_chunk)
2075                                                 T(YAFFS_TRACE_ERROR,
2076                                                   (TSTR("gc: page in gc mismatch: %d %d %d %d"TENDSTR),
2077                                                   old_chunk, matching_chunk, tags.obj_id, tags.chunk_id));
2078
2079                                 }
2080
2081                                 if (!object) {
2082                                         T(YAFFS_TRACE_ERROR,
2083                                           (TSTR
2084                                            ("page %d in gc has no object: %d %d %d "
2085                                             TENDSTR), old_chunk,
2086                                             tags.obj_id, tags.chunk_id, tags.n_bytes));
2087                                 }
2088
2089                                 if (object &&
2090                                     object->deleted &&
2091                                     object->soft_del &&
2092                                     tags.chunk_id != 0) {
2093                                         /* Data chunk in a soft deleted file, throw it away
2094                                          * It's a soft deleted data chunk,
2095                                          * No need to copy this, just forget about it and
2096                                          * fix up the object.
2097                                          */
2098                                          
2099                                         /* Free chunks already includes softdeleted chunks.
2100                                          * How ever this chunk is going to soon be really deleted
2101                                          * which will increment free chunks.
2102                                          * We have to decrement free chunks so this works out properly.
2103                                          */
2104                                         dev->n_free_chunks--;
2105                                         bi->soft_del_pages--;
2106
2107                                         object->n_data_chunks--;
2108
2109                                         if (object->n_data_chunks <= 0) {
2110                                                 /* remeber to clean up the object */
2111                                                 dev->gc_cleanup_list[dev->n_clean_ups] =
2112                                                     tags.obj_id;
2113                                                 dev->n_clean_ups++;
2114                                         }
2115                                         mark_flash = 0;
2116                                 } else if (0) {
2117                                         /* Todo object && object->deleted && object->n_data_chunks == 0 */
2118                                         /* Deleted object header with no data chunks.
2119                                          * Can be discarded and the file deleted.
2120                                          */
2121                                         object->hdr_chunk = 0;
2122                                         yaffs_free_tnode(object->my_dev,
2123                                                         object->variant.
2124                                                         file_variant.top);
2125                                         object->variant.file_variant.top = NULL;
2126                                         yaffs_generic_obj_del(object);
2127
2128                                 } else if (object) {
2129                                         /* It's either a data chunk in a live file or
2130                                          * an ObjectHeader, so we're interested in it.
2131                                          * NB Need to keep the ObjectHeaders of deleted files
2132                                          * until the whole file has been deleted off
2133                                          */
2134                                         tags.serial_number++;
2135
2136                                         dev->n_gc_copies++;
2137
2138                                         if (tags.chunk_id == 0) {
2139                                                 /* It is an object Id,
2140                                                  * We need to nuke the shrinkheader flags first
2141                                                  * Also need to clean up shadowing.
2142                                                  * We no longer want the shrink_header flag since its work is done
2143                                                  * and if it is left in place it will mess up scanning.
2144                                                  */
2145
2146                                                 struct yaffs_obj_hdr *oh;
2147                                                 oh = (struct yaffs_obj_hdr *)buffer;
2148
2149                                                 oh->is_shrink = 0;
2150                                                 tags.extra_is_shrink = 0;
2151
2152                                                 oh->shadows_obj = 0;
2153                                                 oh->inband_shadowed_obj_id = 0;
2154                                                 tags.extra_shadows = 0;
2155
2156                                                 /* Update file size */
2157                                                 if(object->variant_type == YAFFS_OBJECT_TYPE_FILE){
2158                                                         oh->file_size = object->variant.file_variant.file_size;
2159                                                         tags.extra_length = oh->file_size;
2160                                                 }
2161
2162                                                 yaffs_verify_oh(object, oh, &tags, 1);
2163                                                 new_chunk =
2164                                                     yaffs_write_new_chunk(dev,(u8 *) oh, &tags, 1);
2165                                         } else
2166                                                 new_chunk =
2167                                                     yaffs_write_new_chunk(dev, buffer, &tags, 1);
2168
2169                                         if (new_chunk < 0) {
2170                                                 ret_val = YAFFS_FAIL;
2171                                         } else {
2172
2173                                                 /* Ok, now fix up the Tnodes etc. */
2174
2175                                                 if (tags.chunk_id == 0) {
2176                                                         /* It's a header */
2177                                                         object->hdr_chunk =  new_chunk;
2178                                                         object->serial =   tags.serial_number;
2179                                                 } else {
2180                                                         /* It's a data chunk */
2181                                                         int ok;
2182                                                         ok = yaffs_put_chunk_in_file
2183                                                             (object,
2184                                                              tags.chunk_id,
2185                                                              new_chunk, 0);
2186                                                 }
2187                                         }
2188                                 }
2189
2190                                 if (ret_val == YAFFS_OK)
2191                                         yaffs_chunk_del(dev, old_chunk, mark_flash, __LINE__);
2192
2193                         }
2194                 }
2195
2196                 yaffs_release_temp_buffer(dev, buffer, __LINE__);
2197
2198
2199
2200         }
2201
2202         yaffs_verify_collected_blk(dev, bi, block);
2203
2204
2205
2206         if (bi->block_state == YAFFS_BLOCK_STATE_COLLECTING) {
2207                 /*
2208                  * The gc did not complete. Set block state back to FULL
2209                  * because checkpointing does not restore gc.
2210                  */
2211                 bi->block_state = YAFFS_BLOCK_STATE_FULL;
2212         } else {
2213                 /* The gc completed. */
2214                 /* Do any required cleanups */
2215                 for (i = 0; i < dev->n_clean_ups; i++) {
2216                         /* Time to delete the file too */
2217                         object =
2218                             yaffs_find_by_number(dev,
2219                                                      dev->gc_cleanup_list[i]);
2220                         if (object) {
2221                                 yaffs_free_tnode(dev,
2222                                                 object->variant.file_variant.
2223                                                 top);
2224                                 object->variant.file_variant.top = NULL;
2225                                 T(YAFFS_TRACE_GC,
2226                                   (TSTR
2227                                    ("yaffs: About to finally delete object %d"
2228                                     TENDSTR), object->obj_id));
2229                                 yaffs_generic_obj_del(object);
2230                                 object->my_dev->n_deleted_files--;
2231                         }
2232
2233                 }
2234
2235
2236                 chunks_after = yaffs_get_erased_chunks(dev);
2237                 if (chunks_before >= chunks_after) {
2238                         T(YAFFS_TRACE_GC,
2239                           (TSTR
2240                            ("gc did not increase free chunks before %d after %d"
2241                             TENDSTR), chunks_before, chunks_after));
2242                 }
2243                 dev->gc_block = 0;
2244                 dev->gc_chunk = 0;
2245                 dev->n_clean_ups = 0;
2246         }
2247
2248         dev->gc_disable = 0;
2249
2250         return ret_val;
2251 }
2252
2253 /*
2254  * FindBlockForgarbageCollection is used to select the dirtiest block (or close enough)
2255  * for garbage collection.
2256  */
2257
2258 static unsigned yaffs_find_gc_block(struct yaffs_dev *dev,
2259                                         int aggressive,
2260                                         int background)
2261 {
2262         int i;
2263         int iterations;
2264         unsigned selected = 0;
2265         int prioritised = 0;
2266         int prioritised_exist = 0;
2267         struct yaffs_block_info *bi;
2268         int threshold;
2269
2270         /* First let's see if we need to grab a prioritised block */
2271         if (dev->has_pending_prioritised_gc && !aggressive) {
2272                 dev->gc_dirtiest = 0;
2273                 bi = dev->block_info;
2274                 for (i = dev->internal_start_block;
2275                         i <= dev->internal_end_block && !selected;
2276                         i++) {
2277
2278                         if (bi->gc_prioritise) {
2279                                 prioritised_exist = 1;
2280                                 if (bi->block_state == YAFFS_BLOCK_STATE_FULL &&
2281                                    yaffs_block_ok_for_gc(dev, bi)) {
2282                                         selected = i;
2283                                         prioritised = 1;
2284                                 }
2285                         }
2286                         bi++;
2287                 }
2288
2289                 /*
2290                  * If there is a prioritised block and none was selected then
2291                  * this happened because there is at least one old dirty block gumming
2292                  * up the works. Let's gc the oldest dirty block.
2293                  */
2294
2295                 if(prioritised_exist &&
2296                         !selected &&
2297                         dev->oldest_dirty_block > 0)
2298                         selected = dev->oldest_dirty_block;
2299
2300                 if (!prioritised_exist) /* None found, so we can clear this */
2301                         dev->has_pending_prioritised_gc = 0;
2302         }
2303
2304         /* If we're doing aggressive GC then we are happy to take a less-dirty block, and
2305          * search harder.
2306          * else (we're doing a leasurely gc), then we only bother to do this if the
2307          * block has only a few pages in use.
2308          */
2309
2310         if (!selected){
2311                 int pages_used;
2312                 int n_blocks = dev->internal_end_block - dev->internal_start_block + 1;
2313                 if (aggressive){
2314                         threshold = dev->param.chunks_per_block;
2315                         iterations = n_blocks;
2316                 } else {
2317                         int max_threshold;
2318
2319                         if(background)
2320                                 max_threshold = dev->param.chunks_per_block/2;
2321                         else
2322                                 max_threshold = dev->param.chunks_per_block/8;
2323
2324                         if(max_threshold <  YAFFS_GC_PASSIVE_THRESHOLD)
2325                                 max_threshold = YAFFS_GC_PASSIVE_THRESHOLD;
2326
2327                         threshold = background ?
2328                                 (dev->gc_not_done + 2) * 2 : 0;
2329                         if(threshold <YAFFS_GC_PASSIVE_THRESHOLD)
2330                                 threshold = YAFFS_GC_PASSIVE_THRESHOLD;
2331                         if(threshold > max_threshold)
2332                                 threshold = max_threshold;
2333
2334                         iterations = n_blocks / 16 + 1;
2335                         if (iterations > 100)
2336                                 iterations = 100;
2337                 }
2338
2339                 for (i = 0;
2340                         i < iterations &&
2341                         (dev->gc_dirtiest < 1 ||
2342                                 dev->gc_pages_in_use > YAFFS_GC_GOOD_ENOUGH);
2343                         i++) {
2344                         dev->gc_block_finder++;
2345                         if (dev->gc_block_finder < dev->internal_start_block ||
2346                                 dev->gc_block_finder > dev->internal_end_block)
2347                                 dev->gc_block_finder = dev->internal_start_block;
2348
2349                         bi = yaffs_get_block_info(dev, dev->gc_block_finder);
2350
2351                         pages_used = bi->pages_in_use - bi->soft_del_pages;
2352
2353                         if (bi->block_state == YAFFS_BLOCK_STATE_FULL &&
2354                                 pages_used < dev->param.chunks_per_block &&
2355                                 (dev->gc_dirtiest < 1 || pages_used < dev->gc_pages_in_use) &&
2356                                 yaffs_block_ok_for_gc(dev, bi)) {
2357                                 dev->gc_dirtiest = dev->gc_block_finder;
2358                                 dev->gc_pages_in_use = pages_used;
2359                         }
2360                 }
2361
2362                 if(dev->gc_dirtiest > 0 && dev->gc_pages_in_use <= threshold)
2363                         selected = dev->gc_dirtiest;
2364         }
2365
2366         /*
2367          * If nothing has been selected for a while, try selecting the oldest dirty
2368          * because that's gumming up the works.
2369          */
2370
2371         if(!selected && dev->param.is_yaffs2 &&
2372                 dev->gc_not_done >= ( background ? 10 : 20)){
2373                 yaffs2_find_oldest_dirty_seq(dev);
2374                 if(dev->oldest_dirty_block > 0) {
2375                         selected = dev->oldest_dirty_block;
2376                         dev->gc_dirtiest = selected;
2377                         dev->oldest_dirty_gc_count++;
2378                         bi = yaffs_get_block_info(dev, selected);
2379                         dev->gc_pages_in_use =  bi->pages_in_use - bi->soft_del_pages;
2380                 } else
2381                         dev->gc_not_done = 0;
2382         }
2383
2384         if(selected){
2385                 T(YAFFS_TRACE_GC,
2386                   (TSTR("GC Selected block %d with %d free, prioritised:%d" TENDSTR),
2387                   selected,
2388                   dev->param.chunks_per_block - dev->gc_pages_in_use,
2389                   prioritised));
2390
2391                 dev->n_gc_blocks++;
2392                 if(background)
2393                         dev->bg_gcs++;
2394
2395                 dev->gc_dirtiest = 0;
2396                 dev->gc_pages_in_use = 0;
2397                 dev->gc_not_done = 0;
2398                 if(dev->refresh_skip > 0)
2399                         dev->refresh_skip--;
2400         } else{
2401                 dev->gc_not_done++;
2402                 T(YAFFS_TRACE_GC,
2403                   (TSTR("GC none: finder %d skip %d threshold %d dirtiest %d using %d oldest %d%s" TENDSTR),
2404                   dev->gc_block_finder, dev->gc_not_done,
2405                   threshold,
2406                   dev->gc_dirtiest, dev->gc_pages_in_use,
2407                   dev->oldest_dirty_block,
2408                   background ? " bg" : ""));
2409         }
2410
2411         return selected;
2412 }
2413
2414 /* New garbage collector
2415  * If we're very low on erased blocks then we do aggressive garbage collection
2416  * otherwise we do "leasurely" garbage collection.
2417  * Aggressive gc looks further (whole array) and will accept less dirty blocks.
2418  * Passive gc only inspects smaller areas and will only accept more dirty blocks.
2419  *
2420  * The idea is to help clear out space in a more spread-out manner.
2421  * Dunno if it really does anything useful.
2422  */
2423 static int yaffs_check_gc(struct yaffs_dev *dev, int background)
2424 {
2425         int aggressive = 0;
2426         int gc_ok = YAFFS_OK;
2427         int max_tries = 0;
2428         int min_erased;
2429         int erased_chunks;
2430         int checkpt_block_adjust;
2431
2432         if(dev->param.gc_control &&
2433                 (dev->param.gc_control(dev) & 1) == 0)
2434                 return YAFFS_OK;
2435
2436         if (dev->gc_disable) {
2437                 /* Bail out so we don't get recursive gc */
2438                 return YAFFS_OK;
2439         }
2440
2441         /* This loop should pass the first time.
2442          * We'll only see looping here if the collection does not increase space.
2443          */
2444
2445         do {
2446                 max_tries++;
2447
2448                 checkpt_block_adjust = yaffs_calc_checkpt_blocks_required(dev);
2449
2450                 min_erased  = dev->param.n_reserved_blocks + checkpt_block_adjust + 1;
2451                 erased_chunks = dev->n_erased_blocks * dev->param.chunks_per_block;
2452
2453                 /* If we need a block soon then do aggressive gc.*/
2454                 if (dev->n_erased_blocks < min_erased)
2455                         aggressive = 1;
2456                 else {
2457                         if(!background && erased_chunks > (dev->n_free_chunks / 4))
2458                                 break;
2459
2460                         if(dev->gc_skip > 20)
2461                                 dev->gc_skip = 20;
2462                         if(erased_chunks < dev->n_free_chunks/2 ||
2463                                 dev->gc_skip < 1 ||
2464                                 background)
2465                                 aggressive = 0;
2466                         else {
2467                                 dev->gc_skip--;
2468                                 break;
2469                         }
2470                 }
2471
2472                 dev->gc_skip = 5;
2473
2474                 /* If we don't already have a block being gc'd then see if we should start another */
2475
2476                 if (dev->gc_block < 1 && !aggressive) {
2477                         dev->gc_block = yaffs2_find_refresh_block(dev);
2478                         dev->gc_chunk = 0;
2479                         dev->n_clean_ups=0;
2480                 }
2481                 if (dev->gc_block < 1) {
2482                         dev->gc_block = yaffs_find_gc_block(dev, aggressive, background);
2483                         dev->gc_chunk = 0;
2484                         dev->n_clean_ups=0;
2485                 }
2486
2487                 if (dev->gc_block > 0) {
2488                         dev->all_gcs++;
2489                         if (!aggressive)
2490                                 dev->passive_gc_count++;
2491
2492                         T(YAFFS_TRACE_GC,
2493                           (TSTR
2494                            ("yaffs: GC n_erased_blocks %d aggressive %d" TENDSTR),
2495                            dev->n_erased_blocks, aggressive));
2496
2497                         gc_ok = yaffs_gc_block(dev, dev->gc_block, aggressive);
2498                 }
2499
2500                 if (dev->n_erased_blocks < (dev->param.n_reserved_blocks) && dev->gc_block > 0) {
2501                         T(YAFFS_TRACE_GC,
2502                           (TSTR
2503                            ("yaffs: GC !!!no reclaim!!! n_erased_blocks %d after try %d block %d"
2504                             TENDSTR), dev->n_erased_blocks, max_tries, dev->gc_block));
2505                 }
2506         } while ((dev->n_erased_blocks < dev->param.n_reserved_blocks) &&
2507                  (dev->gc_block > 0) &&
2508                  (max_tries < 2));
2509
2510         return aggressive ? gc_ok : YAFFS_OK;
2511 }
2512
2513 /*
2514  * yaffs_bg_gc()
2515  * Garbage collects. Intended to be called from a background thread.
2516  * Returns non-zero if at least half the free chunks are erased.
2517  */
2518 int yaffs_bg_gc(struct yaffs_dev *dev, unsigned urgency)
2519 {
2520         int erased_chunks = dev->n_erased_blocks * dev->param.chunks_per_block;
2521
2522         T(YAFFS_TRACE_BACKGROUND, (TSTR("Background gc %u" TENDSTR),urgency));
2523
2524         yaffs_check_gc(dev, 1);
2525         return erased_chunks > dev->n_free_chunks/2;
2526 }
2527
2528 /*-------------------------  TAGS --------------------------------*/
2529
2530 static int yaffs_tags_match(const struct yaffs_ext_tags *tags, int obj_id,
2531                            int chunk_obj)
2532 {
2533         return (tags->chunk_id == chunk_obj &&
2534                 tags->obj_id == obj_id && !tags->is_deleted) ? 1 : 0;
2535
2536 }
2537
2538
2539 /*-------------------- Data file manipulation -----------------*/
2540
2541 static int yaffs_find_chunk_in_file(struct yaffs_obj *in, int inode_chunk,
2542                                  struct yaffs_ext_tags *tags)
2543 {
2544         /*Get the Tnode, then get the level 0 offset chunk offset */
2545         struct yaffs_tnode *tn;
2546         int the_chunk = -1;
2547         struct yaffs_ext_tags local_tags;
2548         int ret_val = -1;
2549
2550         struct yaffs_dev *dev = in->my_dev;
2551
2552         if (!tags) {
2553                 /* Passed a NULL, so use our own tags space */
2554                 tags = &local_tags;
2555         }
2556
2557         tn = yaffs_find_tnode_0(dev, &in->variant.file_variant, inode_chunk);
2558
2559         if (tn) {
2560                 the_chunk = yaffs_get_group_base(dev, tn, inode_chunk);
2561
2562                 ret_val =
2563                     yaffs_find_chunk_in_group(dev, the_chunk, tags, in->obj_id,
2564                                            inode_chunk);
2565         }
2566         return ret_val;
2567 }
2568
2569 static int yaffs_find_del_file_chunk(struct yaffs_obj *in, int inode_chunk,
2570                                           struct yaffs_ext_tags *tags)
2571 {
2572         /* Get the Tnode, then get the level 0 offset chunk offset */
2573         struct yaffs_tnode *tn;
2574         int the_chunk = -1;
2575         struct yaffs_ext_tags local_tags;
2576
2577         struct yaffs_dev *dev = in->my_dev;
2578         int ret_val = -1;
2579
2580         if (!tags) {
2581                 /* Passed a NULL, so use our own tags space */
2582                 tags = &local_tags;
2583         }
2584
2585         tn = yaffs_find_tnode_0(dev, &in->variant.file_variant, inode_chunk);
2586
2587         if (tn) {
2588
2589                 the_chunk = yaffs_get_group_base(dev, tn, inode_chunk);
2590
2591                 ret_val =
2592                     yaffs_find_chunk_in_group(dev, the_chunk, tags, in->obj_id,
2593                                            inode_chunk);
2594
2595                 /* Delete the entry in the filestructure (if found) */
2596                 if (ret_val != -1)
2597                         yaffs_load_tnode_0(dev, tn, inode_chunk, 0);
2598         }
2599
2600         return ret_val;
2601 }
2602
2603
2604 int yaffs_put_chunk_in_file(struct yaffs_obj *in, int inode_chunk,
2605                                 int nand_chunk, int in_scan)
2606 {
2607         /* NB in_scan is zero unless scanning.
2608          * For forward scanning, in_scan is > 0;
2609          * for backward scanning in_scan is < 0
2610          *
2611          * nand_chunk = 0 is a dummy insert to make sure the tnodes are there.
2612          */
2613
2614         struct yaffs_tnode *tn;
2615         struct yaffs_dev *dev = in->my_dev;
2616         int existing_cunk;
2617         struct yaffs_ext_tags existing_tags;
2618         struct yaffs_ext_tags new_tags;
2619         unsigned existing_serial, new_serial;
2620
2621         if (in->variant_type != YAFFS_OBJECT_TYPE_FILE) {
2622                 /* Just ignore an attempt at putting a chunk into a non-file during scanning
2623                  * If it is not during Scanning then something went wrong!
2624                  */
2625                 if (!in_scan) {
2626                         T(YAFFS_TRACE_ERROR,
2627                           (TSTR
2628                            ("yaffs tragedy:attempt to put data chunk into a non-file"
2629                             TENDSTR)));
2630                         YBUG();
2631                 }
2632
2633                 yaffs_chunk_del(dev, nand_chunk, 1, __LINE__);
2634                 return YAFFS_OK;
2635         }
2636
2637         tn = yaffs_add_find_tnode_0(dev,
2638                                         &in->variant.file_variant,
2639                                         inode_chunk,
2640                                         NULL);
2641         if (!tn)
2642                 return YAFFS_FAIL;
2643         
2644         if(!nand_chunk)
2645                 /* Dummy insert, bail now */
2646                 return YAFFS_OK;
2647
2648         existing_cunk = yaffs_get_group_base(dev, tn, inode_chunk);
2649
2650         if (in_scan != 0) {
2651                 /* If we're scanning then we need to test for duplicates
2652                  * NB This does not need to be efficient since it should only ever
2653                  * happen when the power fails during a write, then only one
2654                  * chunk should ever be affected.
2655                  *
2656                  * Correction for YAFFS2: This could happen quite a lot and we need to think about efficiency! TODO
2657                  * Update: For backward scanning we don't need to re-read tags so this is quite cheap.
2658                  */
2659
2660                 if (existing_cunk > 0) {
2661                         /* NB Right now existing chunk will not be real chunk_id if the chunk group size > 1
2662                          *    thus we have to do a FindChunkInFile to get the real chunk id.
2663                          *
2664                          * We have a duplicate now we need to decide which one to use:
2665                          *
2666                          * Backwards scanning YAFFS2: The old one is what we use, dump the new one.
2667                          * Forward scanning YAFFS2: The new one is what we use, dump the old one.
2668                          * YAFFS1: Get both sets of tags and compare serial numbers.
2669                          */
2670
2671                         if (in_scan > 0) {
2672                                 /* Only do this for forward scanning */
2673                                 yaffs_rd_chunk_tags_nand(dev,
2674                                                                 nand_chunk,
2675                                                                 NULL, &new_tags);
2676
2677                                 /* Do a proper find */
2678                                 existing_cunk =
2679                                     yaffs_find_chunk_in_file(in, inode_chunk,
2680                                                           &existing_tags);
2681                         }
2682
2683                         if (existing_cunk <= 0) {
2684                                 /*Hoosterman - how did this happen? */
2685
2686                                 T(YAFFS_TRACE_ERROR,
2687                                   (TSTR
2688                                    ("yaffs tragedy: existing chunk < 0 in scan"
2689                                     TENDSTR)));
2690
2691                         }
2692
2693                         /* NB The deleted flags should be false, otherwise the chunks will
2694                          * not be loaded during a scan
2695                          */
2696
2697                         if (in_scan > 0) {
2698                                 new_serial = new_tags.serial_number;
2699                                 existing_serial = existing_tags.serial_number;
2700                         }
2701
2702                         if ((in_scan > 0) &&
2703                             (existing_cunk <= 0 ||
2704                              ((existing_serial + 1) & 3) == new_serial)) {
2705                                 /* Forward scanning.
2706                                  * Use new
2707                                  * Delete the old one and drop through to update the tnode
2708                                  */
2709                                 yaffs_chunk_del(dev, existing_cunk, 1,
2710                                                   __LINE__);
2711                         } else {
2712                                 /* Backward scanning or we want to use the existing one
2713                                  * Use existing.
2714                                  * Delete the new one and return early so that the tnode isn't changed
2715                                  */
2716                                 yaffs_chunk_del(dev, nand_chunk, 1,
2717                                                   __LINE__);
2718                                 return YAFFS_OK;
2719                         }
2720                 }
2721
2722         }
2723
2724         if (existing_cunk == 0)
2725                 in->n_data_chunks++;
2726
2727         yaffs_load_tnode_0(dev, tn, inode_chunk, nand_chunk);
2728
2729         return YAFFS_OK;
2730 }
2731
2732 static int yaffs_rd_data_obj(struct yaffs_obj *in, int inode_chunk,
2733                                         u8 *buffer)
2734 {
2735         int nand_chunk = yaffs_find_chunk_in_file(in, inode_chunk, NULL);
2736
2737         if (nand_chunk >= 0)
2738                 return yaffs_rd_chunk_tags_nand(in->my_dev, nand_chunk,
2739                                                 buffer, NULL);
2740         else {
2741                 T(YAFFS_TRACE_NANDACCESS,
2742                   (TSTR("Chunk %d not found zero instead" TENDSTR),
2743                    nand_chunk));
2744                 /* get sane (zero) data if you read a hole */
2745                 memset(buffer, 0, in->my_dev->data_bytes_per_chunk);
2746                 return 0;
2747         }
2748
2749 }
2750
2751 void yaffs_chunk_del(struct yaffs_dev *dev, int chunk_id, int mark_flash, int lyn)
2752 {
2753         int block;
2754         int page;
2755         struct yaffs_ext_tags tags;
2756         struct yaffs_block_info *bi;
2757
2758         if (chunk_id <= 0)
2759                 return;
2760
2761         dev->n_deletions++;
2762         block = chunk_id / dev->param.chunks_per_block;
2763         page = chunk_id % dev->param.chunks_per_block;
2764
2765
2766         if (!yaffs_check_chunk_bit(dev, block, page))
2767                 T(YAFFS_TRACE_VERIFY,
2768                         (TSTR("Deleting invalid chunk %d"TENDSTR),
2769                          chunk_id));
2770
2771         bi = yaffs_get_block_info(dev, block);
2772         
2773         yaffs2_update_oldest_dirty_seq(dev, block, bi);
2774
2775         T(YAFFS_TRACE_DELETION,
2776           (TSTR("line %d delete of chunk %d" TENDSTR), lyn, chunk_id));
2777
2778         if (!dev->param.is_yaffs2 && mark_flash &&
2779             bi->block_state != YAFFS_BLOCK_STATE_COLLECTING) {
2780
2781                 yaffs_init_tags(&tags);
2782
2783                 tags.is_deleted = 1;
2784
2785                 yaffs_wr_chunk_tags_nand(dev, chunk_id, NULL, &tags);
2786                 yaffs_handle_chunk_update(dev, chunk_id, &tags);
2787         } else {
2788                 dev->n_unmarked_deletions++;
2789         }
2790
2791         /* Pull out of the management area.
2792          * If the whole block became dirty, this will kick off an erasure.
2793          */
2794         if (bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING ||
2795             bi->block_state == YAFFS_BLOCK_STATE_FULL ||
2796             bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCANNING ||
2797             bi->block_state == YAFFS_BLOCK_STATE_COLLECTING) {
2798                 dev->n_free_chunks++;
2799
2800                 yaffs_clear_chunk_bit(dev, block, page);
2801
2802                 bi->pages_in_use--;
2803
2804                 if (bi->pages_in_use == 0 &&
2805                     !bi->has_shrink_hdr &&
2806                     bi->block_state != YAFFS_BLOCK_STATE_ALLOCATING &&
2807                     bi->block_state != YAFFS_BLOCK_STATE_NEEDS_SCANNING) {
2808                         yaffs_block_became_dirty(dev, block);
2809                 }
2810
2811         }
2812
2813 }
2814
2815 static int yaffs_wr_data_obj(struct yaffs_obj *in, int inode_chunk,
2816                                         const u8 *buffer, int n_bytes,
2817                                         int use_reserve)
2818 {
2819         /* Find old chunk Need to do this to get serial number
2820          * Write new one and patch into tree.
2821          * Invalidate old tags.
2822          */
2823
2824         int prev_chunk_id;
2825         struct yaffs_ext_tags prev_tags;
2826
2827         int new_chunk_id;
2828         struct yaffs_ext_tags new_tags;
2829
2830         struct yaffs_dev *dev = in->my_dev;
2831
2832         yaffs_check_gc(dev,0);
2833
2834         /* Get the previous chunk at this location in the file if it exists.
2835          * If it does not exist then put a zero into the tree. This creates
2836          * the tnode now, rather than later when it is harder to clean up.
2837          */
2838         prev_chunk_id = yaffs_find_chunk_in_file(in, inode_chunk, &prev_tags);
2839         if(prev_chunk_id < 1 &&
2840                 !yaffs_put_chunk_in_file(in, inode_chunk, 0, 0))
2841                 return 0;
2842
2843         /* Set up new tags */
2844         yaffs_init_tags(&new_tags);
2845
2846         new_tags.chunk_id = inode_chunk;
2847         new_tags.obj_id = in->obj_id;
2848         new_tags.serial_number =
2849             (prev_chunk_id > 0) ? prev_tags.serial_number + 1 : 1;
2850         new_tags.n_bytes = n_bytes;
2851
2852         if (n_bytes < 1 || n_bytes > dev->param.total_bytes_per_chunk) {
2853                 T(YAFFS_TRACE_ERROR,
2854                 (TSTR("Writing %d bytes to chunk!!!!!!!!!" TENDSTR), n_bytes));
2855                 YBUG();
2856         }
2857         
2858                 
2859         new_chunk_id =
2860             yaffs_write_new_chunk(dev, buffer, &new_tags,
2861                                               use_reserve);
2862
2863         if (new_chunk_id > 0) {
2864                 yaffs_put_chunk_in_file(in, inode_chunk, new_chunk_id, 0);
2865
2866                 if (prev_chunk_id > 0)
2867                         yaffs_chunk_del(dev, prev_chunk_id, 1, __LINE__);
2868
2869                 yaffs_verify_file_sane(in);
2870         }
2871         return new_chunk_id;
2872
2873 }
2874
2875 /* UpdateObjectHeader updates the header on NAND for an object.
2876  * If name is not NULL, then that new name is used.
2877  */
2878 int yaffs_update_oh(struct yaffs_obj *in, const YCHAR *name, int force,
2879                              int is_shrink, int shadows, struct yaffs_xattr_mod *xmod)
2880 {
2881
2882         struct yaffs_block_info *bi;
2883
2884         struct yaffs_dev *dev = in->my_dev;
2885
2886         int prev_chunk_id;
2887         int ret_val = 0;
2888         int result = 0;
2889
2890         int new_chunk_id;
2891         struct yaffs_ext_tags new_tags;
2892         struct yaffs_ext_tags old_tags;
2893         const YCHAR *alias = NULL;
2894
2895         u8 *buffer = NULL;
2896         YCHAR old_name[YAFFS_MAX_NAME_LENGTH + 1];
2897
2898         struct yaffs_obj_hdr *oh = NULL;
2899
2900         yaffs_strcpy(old_name, _Y("silly old name"));
2901
2902
2903         if (!in->fake ||
2904                 in == dev->root_dir || /* The root_dir should also be saved */
2905                 force  || xmod) {
2906
2907                 yaffs_check_gc(dev,0);
2908                 yaffs_check_obj_details_loaded(in);
2909
2910                 buffer = yaffs_get_temp_buffer(in->my_dev, __LINE__);
2911                 oh = (struct yaffs_obj_hdr *) buffer;
2912
2913                 prev_chunk_id = in->hdr_chunk;
2914
2915                 if (prev_chunk_id > 0) {
2916                         result = yaffs_rd_chunk_tags_nand(dev, prev_chunk_id,
2917                                                         buffer, &old_tags);
2918
2919                         yaffs_verify_oh(in, oh, &old_tags, 0);
2920
2921                         memcpy(old_name, oh->name, sizeof(oh->name));
2922                         memset(buffer, 0xFF, sizeof(struct yaffs_obj_hdr));
2923                 } else
2924                         memset(buffer, 0xFF, dev->data_bytes_per_chunk);
2925
2926                 oh->type = in->variant_type;
2927                 oh->yst_mode = in->yst_mode;
2928                 oh->shadows_obj = oh->inband_shadowed_obj_id = shadows;
2929
2930                 yaffs_load_attribs_oh(oh,in);
2931
2932                 if (in->parent)
2933                         oh->parent_obj_id = in->parent->obj_id;
2934                 else
2935                         oh->parent_obj_id = 0;
2936
2937                 if (name && *name) {
2938                         memset(oh->name, 0, sizeof(oh->name));
2939                         yaffs_load_oh_from_name(dev,oh->name,name);
2940                 } else if (prev_chunk_id > 0)
2941                         memcpy(oh->name, old_name, sizeof(oh->name));
2942                 else
2943                         memset(oh->name, 0, sizeof(oh->name));
2944
2945                 oh->is_shrink = is_shrink;
2946
2947                 switch (in->variant_type) {
2948                 case YAFFS_OBJECT_TYPE_UNKNOWN:
2949                         /* Should not happen */
2950                         break;
2951                 case YAFFS_OBJECT_TYPE_FILE:
2952                         oh->file_size =
2953                             (oh->parent_obj_id == YAFFS_OBJECTID_DELETED
2954                              || oh->parent_obj_id ==
2955                              YAFFS_OBJECTID_UNLINKED) ? 0 : in->variant.
2956                             file_variant.file_size;
2957                         break;
2958                 case YAFFS_OBJECT_TYPE_HARDLINK:
2959                         oh->equiv_id =
2960                             in->variant.hardlink_variant.equiv_id;
2961                         break;
2962                 case YAFFS_OBJECT_TYPE_SPECIAL:
2963                         /* Do nothing */
2964                         break;
2965                 case YAFFS_OBJECT_TYPE_DIRECTORY:
2966                         /* Do nothing */
2967                         break;
2968                 case YAFFS_OBJECT_TYPE_SYMLINK:
2969                         alias = in->variant.symlink_variant.alias;
2970                         if(!alias)
2971                                 alias = _Y("no alias");
2972                         yaffs_strncpy(oh->alias,
2973                                         alias,
2974                                       YAFFS_MAX_ALIAS_LENGTH);
2975                         oh->alias[YAFFS_MAX_ALIAS_LENGTH] = 0;
2976                         break;
2977                 }
2978
2979                 /* process any xattrib modifications */
2980                 if(xmod)
2981                         yaffs_apply_xattrib_mod(in, (char *)buffer, xmod);
2982
2983
2984                 /* Tags */
2985                 yaffs_init_tags(&new_tags);
2986                 in->serial++;
2987                 new_tags.chunk_id = 0;
2988                 new_tags.obj_id = in->obj_id;
2989                 new_tags.serial_number = in->serial;
2990
2991                 /* Add extra info for file header */
2992
2993                 new_tags.extra_available = 1;
2994                 new_tags.extra_parent_id = oh->parent_obj_id;
2995                 new_tags.extra_length = oh->file_size;
2996                 new_tags.extra_is_shrink = oh->is_shrink;
2997                 new_tags.extra_equiv_id = oh->equiv_id;
2998                 new_tags.extra_shadows = (oh->shadows_obj > 0) ? 1 : 0;
2999                 new_tags.extra_obj_type = in->variant_type;
3000
3001                 yaffs_verify_oh(in, oh, &new_tags, 1);
3002
3003                 /* Create new chunk in NAND */
3004                 new_chunk_id =
3005                     yaffs_write_new_chunk(dev, buffer, &new_tags,
3006                                                       (prev_chunk_id > 0) ? 1 : 0);
3007
3008                 if (new_chunk_id >= 0) {
3009
3010                         in->hdr_chunk = new_chunk_id;
3011
3012                         if (prev_chunk_id > 0) {
3013                                 yaffs_chunk_del(dev, prev_chunk_id, 1,
3014                                                   __LINE__);
3015                         }
3016
3017                         if (!yaffs_obj_cache_dirty(in))
3018                                 in->dirty = 0;
3019
3020                         /* If this was a shrink, then mark the block that the chunk lives on */
3021                         if (is_shrink) {
3022                                 bi = yaffs_get_block_info(in->my_dev,
3023                                         new_chunk_id / in->my_dev->param.chunks_per_block);
3024                                 bi->has_shrink_hdr = 1;
3025                         }
3026
3027                 }
3028
3029                 ret_val = new_chunk_id;
3030
3031         }
3032
3033         if (buffer)
3034                 yaffs_release_temp_buffer(dev, buffer, __LINE__);
3035
3036         return ret_val;
3037 }
3038
3039 /*------------------------ Short Operations Cache ----------------------------------------
3040  *   In many situations where there is no high level buffering  a lot of
3041  *   reads might be short sequential reads, and a lot of writes may be short
3042  *   sequential writes. eg. scanning/writing a jpeg file.
3043  *   In these cases, a short read/write cache can provide a huge perfomance
3044  *   benefit with dumb-as-a-rock code.
3045  *   In Linux, the page cache provides read buffering and the short op cache 
3046  *   provides write buffering.
3047  *
3048  *   There are a limited number (~10) of cache chunks per device so that we don't
3049  *   need a very intelligent search.
3050  */
3051
3052 static int yaffs_obj_cache_dirty(struct yaffs_obj *obj)
3053 {
3054         struct yaffs_dev *dev = obj->my_dev;
3055         int i;
3056         struct yaffs_cache *cache;
3057         int n_caches = obj->my_dev->param.n_caches;
3058
3059         for (i = 0; i < n_caches; i++) {
3060                 cache = &dev->cache[i];
3061                 if (cache->object == obj &&
3062                     cache->dirty)
3063                         return 1;
3064         }
3065
3066         return 0;
3067 }
3068
3069
3070 static void yaffs_flush_file_cache(struct yaffs_obj *obj)
3071 {
3072         struct yaffs_dev *dev = obj->my_dev;
3073         int lowest = -99;       /* Stop compiler whining. */
3074         int i;
3075         struct yaffs_cache *cache;
3076         int chunk_written = 0;
3077         int n_caches = obj->my_dev->param.n_caches;
3078
3079         if (n_caches > 0) {
3080                 do {
3081                         cache = NULL;
3082
3083                         /* Find the dirty cache for this object with the lowest chunk id. */
3084                         for (i = 0; i < n_caches; i++) {
3085                                 if (dev->cache[i].object == obj &&
3086                                     dev->cache[i].dirty) {
3087                                         if (!cache
3088                                             || dev->cache[i].chunk_id <
3089                                             lowest) {
3090                                                 cache = &dev->cache[i];
3091                                                 lowest = cache->chunk_id;
3092                                         }
3093                                 }
3094                         }
3095
3096                         if (cache && !cache->locked) {
3097                                 /* Write it out and free it up */
3098
3099                                 chunk_written =
3100                                     yaffs_wr_data_obj(cache->object,
3101                                                                  cache->chunk_id,
3102                                                                  cache->data,
3103                                                                  cache->n_bytes,
3104                                                                  1);
3105                                 cache->dirty = 0;
3106                                 cache->object = NULL;
3107                         }
3108
3109                 } while (cache && chunk_written > 0);
3110
3111                 if (cache) {
3112                         /* Hoosterman, disk full while writing cache out. */
3113                         T(YAFFS_TRACE_ERROR,
3114                           (TSTR("yaffs tragedy: no space during cache write" TENDSTR)));
3115
3116                 }
3117         }
3118
3119 }
3120
3121 /*yaffs_flush_whole_cache(dev)
3122  *
3123  *
3124  */
3125
3126 void yaffs_flush_whole_cache(struct yaffs_dev *dev)
3127 {
3128         struct yaffs_obj *obj;
3129         int n_caches = dev->param.n_caches;
3130         int i;
3131
3132         /* Find a dirty object in the cache and flush it...
3133          * until there are no further dirty objects.
3134          */
3135         do {
3136                 obj = NULL;
3137                 for (i = 0; i < n_caches && !obj; i++) {
3138                         if (dev->cache[i].object &&
3139                             dev->cache[i].dirty)
3140                                 obj = dev->cache[i].object;
3141
3142                 }
3143                 if (obj)
3144                         yaffs_flush_file_cache(obj);
3145
3146         } while (obj);
3147
3148 }
3149
3150
3151 /* Grab us a cache chunk for use.
3152  * First look for an empty one.
3153  * Then look for the least recently used non-dirty one.
3154  * Then look for the least recently used dirty one...., flush and look again.
3155  */
3156 static struct yaffs_cache *yaffs_grab_chunk_worker(struct yaffs_dev *dev)
3157 {
3158         int i;
3159
3160         if (dev->param.n_caches > 0) {
3161                 for (i = 0; i < dev->param.n_caches; i++) {
3162                         if (!dev->cache[i].object)
3163                                 return &dev->cache[i];
3164                 }
3165         }
3166
3167         return NULL;
3168 }
3169
3170 static struct yaffs_cache *yaffs_grab_chunk_cache(struct yaffs_dev *dev)
3171 {
3172         struct yaffs_cache *cache;
3173         struct yaffs_obj *the_obj;
3174         int usage;
3175         int i;
3176         int pushout;
3177
3178         if (dev->param.n_caches > 0) {
3179                 /* Try find a non-dirty one... */
3180
3181                 cache = yaffs_grab_chunk_worker(dev);
3182
3183                 if (!cache) {
3184                         /* They were all dirty, find the last recently used object and flush
3185                          * its cache, then  find again.
3186                          * NB what's here is not very accurate, we actually flush the object
3187                          * the last recently used page.
3188                          */
3189
3190                         /* With locking we can't assume we can use entry zero */
3191
3192                         the_obj = NULL;
3193                         usage = -1;
3194                         cache = NULL;
3195                         pushout = -1;
3196
3197                         for (i = 0; i < dev->param.n_caches; i++) {
3198                                 if (dev->cache[i].object &&
3199                                     !dev->cache[i].locked &&
3200                                     (dev->cache[i].last_use < usage || !cache)) {
3201                                         usage = dev->cache[i].last_use;
3202                                         the_obj = dev->cache[i].object;
3203                                         cache = &dev->cache[i];
3204                                         pushout = i;
3205                                 }
3206                         }
3207
3208                         if (!cache || cache->dirty) {
3209                                 /* Flush and try again */
3210                                 yaffs_flush_file_cache(the_obj);
3211                                 cache = yaffs_grab_chunk_worker(dev);
3212                         }
3213
3214                 }
3215                 return cache;
3216         } else
3217                 return NULL;
3218
3219 }
3220
3221 /* Find a cached chunk */
3222 static struct yaffs_cache *yaffs_find_chunk_cache(const struct yaffs_obj *obj,
3223                                               int chunk_id)
3224 {
3225         struct yaffs_dev *dev = obj->my_dev;
3226         int i;
3227         if (dev->param.n_caches > 0) {
3228                 for (i = 0; i < dev->param.n_caches; i++) {
3229                         if (dev->cache[i].object == obj &&
3230                             dev->cache[i].chunk_id == chunk_id) {
3231                                 dev->cache_hits++;
3232
3233                                 return &dev->cache[i];
3234                         }
3235                 }
3236         }
3237         return NULL;
3238 }
3239
3240 /* Mark the chunk for the least recently used algorithym */
3241 static void yaffs_use_cache(struct yaffs_dev *dev, struct yaffs_cache *cache,
3242                                 int is_write)
3243 {
3244
3245         if (dev->param.n_caches > 0) {
3246                 if (dev->cache_last_use < 0 || dev->cache_last_use > 100000000) {
3247                         /* Reset the cache usages */
3248                         int i;
3249                         for (i = 1; i < dev->param.n_caches; i++)
3250                                 dev->cache[i].last_use = 0;
3251
3252                         dev->cache_last_use = 0;
3253                 }
3254
3255                 dev->cache_last_use++;
3256
3257                 cache->last_use = dev->cache_last_use;
3258
3259                 if (is_write)
3260                         cache->dirty = 1;
3261         }
3262 }
3263
3264 /* Invalidate a single cache page.
3265  * Do this when a whole page gets written,
3266  * ie the short cache for this page is no longer valid.
3267  */
3268 static void yaffs_invalidate_chunk_cache(struct yaffs_obj *object, int chunk_id)
3269 {
3270         if (object->my_dev->param.n_caches > 0) {
3271                 struct yaffs_cache *cache = yaffs_find_chunk_cache(object, chunk_id);
3272
3273                 if (cache)
3274                         cache->object = NULL;
3275         }
3276 }
3277
3278 /* Invalidate all the cache pages associated with this object
3279  * Do this whenever ther file is deleted or resized.
3280  */
3281 static void yaffs_invalidate_whole_cache(struct yaffs_obj *in)
3282 {
3283         int i;
3284         struct yaffs_dev *dev = in->my_dev;
3285
3286         if (dev->param.n_caches > 0) {
3287                 /* Invalidate it. */
3288                 for (i = 0; i < dev->param.n_caches; i++) {
3289                         if (dev->cache[i].object == in)
3290                                 dev->cache[i].object = NULL;
3291                 }
3292         }
3293 }
3294
3295
3296 /*--------------------- File read/write ------------------------
3297  * Read and write have very similar structures.
3298  * In general the read/write has three parts to it
3299  * An incomplete chunk to start with (if the read/write is not chunk-aligned)
3300  * Some complete chunks
3301  * An incomplete chunk to end off with
3302  *
3303  * Curve-balls: the first chunk might also be the last chunk.
3304  */
3305
3306 int yaffs_file_rd(struct yaffs_obj *in, u8 *buffer, loff_t offset,
3307                         int n_bytes)
3308 {
3309
3310         int chunk;
3311         u32 start;
3312         int n_copy;
3313         int n = n_bytes;
3314         int n_done = 0;
3315         struct yaffs_cache *cache;
3316
3317         struct yaffs_dev *dev;
3318
3319         dev = in->my_dev;
3320
3321         while (n > 0) {
3322                 /* chunk = offset / dev->data_bytes_per_chunk + 1; */
3323                 /* start = offset % dev->data_bytes_per_chunk; */
3324                 yaffs_addr_to_chunk(dev, offset, &chunk, &start);
3325                 chunk++;
3326
3327                 /* OK now check for the curveball where the start and end are in
3328                  * the same chunk.
3329                  */
3330                 if ((start + n) < dev->data_bytes_per_chunk)
3331                         n_copy = n;
3332                 else
3333                         n_copy = dev->data_bytes_per_chunk - start;
3334
3335                 cache = yaffs_find_chunk_cache(in, chunk);
3336
3337                 /* If the chunk is already in the cache or it is less than a whole chunk
3338                  * or we're using inband tags then use the cache (if there is caching)
3339                  * else bypass the cache.
3340                  */
3341                 if (cache || n_copy != dev->data_bytes_per_chunk || dev->param.inband_tags) {
3342                         if (dev->param.n_caches > 0) {
3343
3344                                 /* If we can't find the data in the cache, then load it up. */
3345
3346                                 if (!cache) {
3347                                         cache = yaffs_grab_chunk_cache(in->my_dev);
3348                                         cache->object = in;
3349                                         cache->chunk_id = chunk;
3350                                         cache->dirty = 0;
3351                                         cache->locked = 0;
3352                                         yaffs_rd_data_obj(in, chunk,
3353                                                                       cache->
3354                                                                       data);
3355                                         cache->n_bytes = 0;
3356                                 }
3357
3358                                 yaffs_use_cache(dev, cache, 0);
3359
3360                                 cache->locked = 1;
3361
3362
3363                                 memcpy(buffer, &cache->data[start], n_copy);
3364
3365                                 cache->locked = 0;
3366                         } else {
3367                                 /* Read into the local buffer then copy..*/
3368
3369                                 u8 *local_buffer =
3370                                     yaffs_get_temp_buffer(dev, __LINE__);
3371                                 yaffs_rd_data_obj(in, chunk,
3372                                                               local_buffer);
3373
3374                                 memcpy(buffer, &local_buffer[start], n_copy);
3375
3376
3377                                 yaffs_release_temp_buffer(dev, local_buffer,
3378                                                         __LINE__);
3379                         }
3380
3381                 } else {
3382
3383                         /* A full chunk. Read directly into the supplied buffer. */
3384                         yaffs_rd_data_obj(in, chunk, buffer);
3385
3386                 }
3387
3388                 n -= n_copy;
3389                 offset += n_copy;
3390                 buffer += n_copy;
3391                 n_done += n_copy;
3392
3393         }
3394
3395         return n_done;
3396 }
3397
3398 int yaffs_do_file_wr(struct yaffs_obj *in, const u8 *buffer, loff_t offset,
3399                         int n_bytes, int write_trhrough)
3400 {
3401
3402         int chunk;
3403         u32 start;
3404         int n_copy;
3405         int n = n_bytes;
3406         int n_done = 0;
3407         int n_writeback;
3408         int start_write = offset;
3409         int chunk_written = 0;
3410         u32 n_bytes_read;
3411         u32 chunk_start;
3412
3413         struct yaffs_dev *dev;
3414
3415         dev = in->my_dev;
3416
3417         while (n > 0 && chunk_written >= 0) {
3418                 yaffs_addr_to_chunk(dev, offset, &chunk, &start);
3419
3420                 if (chunk * dev->data_bytes_per_chunk + start != offset ||
3421                                 start >= dev->data_bytes_per_chunk) {
3422                         T(YAFFS_TRACE_ERROR, (
3423                            TSTR("AddrToChunk of offset %d gives chunk %d start %d"
3424                            TENDSTR),
3425                            (int)offset, chunk, start));
3426                 }
3427                 chunk++; /* File pos to chunk in file offset */
3428
3429                 /* OK now check for the curveball where the start and end are in
3430                  * the same chunk.
3431                  */
3432
3433                 if ((start + n) < dev->data_bytes_per_chunk) {
3434                         n_copy = n;
3435
3436                         /* Now folks, to calculate how many bytes to write back....
3437                          * If we're overwriting and not writing to then end of file then
3438                          * we need to write back as much as was there before.
3439                          */
3440
3441                         chunk_start = ((chunk - 1) * dev->data_bytes_per_chunk);
3442
3443                         if (chunk_start > in->variant.file_variant.file_size)
3444                                 n_bytes_read = 0; /* Past end of file */
3445                         else
3446                                 n_bytes_read = in->variant.file_variant.file_size - chunk_start;
3447
3448                         if (n_bytes_read > dev->data_bytes_per_chunk)
3449                                 n_bytes_read = dev->data_bytes_per_chunk;
3450
3451                         n_writeback =
3452                             (n_bytes_read >
3453                              (start + n)) ? n_bytes_read : (start + n);
3454
3455                         if (n_writeback < 0 || n_writeback > dev->data_bytes_per_chunk)
3456                                 YBUG();
3457
3458                 } else {
3459                         n_copy = dev->data_bytes_per_chunk - start;
3460                         n_writeback = dev->data_bytes_per_chunk;
3461                 }
3462
3463                 if (n_copy != dev->data_bytes_per_chunk || dev->param.inband_tags) {
3464                         /* An incomplete start or end chunk (or maybe both start and end chunk),
3465                          * or we're using inband tags, so we want to use the cache buffers.
3466                          */
3467                         if (dev->param.n_caches > 0) {
3468                                 struct yaffs_cache *cache;
3469                                 /* If we can't find the data in the cache, then load the cache */
3470                                 cache = yaffs_find_chunk_cache(in, chunk);
3471
3472                                 if (!cache
3473                                     && yaffs_check_alloc_available(dev, 1)) {
3474                                         cache = yaffs_grab_chunk_cache(dev);
3475                                         cache->object = in;
3476                                         cache->chunk_id = chunk;
3477                                         cache->dirty = 0;
3478                                         cache->locked = 0;
3479                                         yaffs_rd_data_obj(in, chunk,
3480                                                                       cache->data);
3481                                 } else if (cache &&
3482                                         !cache->dirty &&
3483                                         !yaffs_check_alloc_available(dev, 1)) {
3484                                         /* Drop the cache if it was a read cache item and
3485                                          * no space check has been made for it.
3486                                          */
3487                                          cache = NULL;
3488                                 }
3489
3490                                 if (cache) {
3491                                         yaffs_use_cache(dev, cache, 1);
3492                                         cache->locked = 1;
3493
3494
3495                                         memcpy(&cache->data[start], buffer,
3496                                                n_copy);
3497
3498
3499                                         cache->locked = 0;
3500                                         cache->n_bytes = n_writeback;
3501
3502                                         if (write_trhrough) {
3503                                                 chunk_written =
3504                                                     yaffs_wr_data_obj
3505                                                     (cache->object,
3506                                                      cache->chunk_id,
3507                                                      cache->data, cache->n_bytes,
3508                                                      1);
3509                                                 cache->dirty = 0;
3510                                         }
3511
3512                                 } else {
3513                                         chunk_written = -1;     /* fail the write */
3514                                 }
3515                         } else {
3516                                 /* An incomplete start or end chunk (or maybe both start and end chunk)
3517                                  * Read into the local buffer then copy, then copy over and write back.
3518                                  */
3519
3520                                 u8 *local_buffer =
3521                                     yaffs_get_temp_buffer(dev, __LINE__);
3522
3523                                 yaffs_rd_data_obj(in, chunk,
3524                                                               local_buffer);
3525
3526
3527
3528                                 memcpy(&local_buffer[start], buffer, n_copy);
3529
3530                                 chunk_written =
3531                                     yaffs_wr_data_obj(in, chunk,
3532                                                                  local_buffer,
3533                                                                  n_writeback,
3534                                                                  0);
3535
3536                                 yaffs_release_temp_buffer(dev, local_buffer,
3537                                                         __LINE__);
3538
3539                         }
3540
3541                 } else {
3542                         /* A full chunk. Write directly from the supplied buffer. */
3543
3544
3545
3546                         chunk_written =
3547                             yaffs_wr_data_obj(in, chunk, buffer,
3548                                                          dev->data_bytes_per_chunk,
3549                                                          0);
3550
3551                         /* Since we've overwritten the cached data, we better invalidate it. */
3552                         yaffs_invalidate_chunk_cache(in, chunk);
3553                 }
3554
3555                 if (chunk_written >= 0) {
3556                         n -= n_copy;
3557                         offset += n_copy;
3558                         buffer += n_copy;
3559                         n_done += n_copy;
3560                 }
3561
3562         }
3563
3564         /* Update file object */
3565
3566         if ((start_write + n_done) > in->variant.file_variant.file_size)
3567                 in->variant.file_variant.file_size = (start_write + n_done);
3568
3569         in->dirty = 1;
3570
3571         return n_done;
3572 }
3573
3574 int yaffs_wr_file(struct yaffs_obj *in, const u8 *buffer, loff_t offset,
3575                         int n_bytes, int write_trhrough)
3576 {
3577         yaffs2_handle_hole(in,offset);
3578         return yaffs_do_file_wr(in,buffer,offset,n_bytes,write_trhrough);
3579 }
3580
3581
3582
3583 /* ---------------------- File resizing stuff ------------------ */
3584
3585 static void yaffs_prune_chunks(struct yaffs_obj *in, int new_size)
3586 {
3587
3588         struct yaffs_dev *dev = in->my_dev;
3589         int old_size = in->variant.file_variant.file_size;
3590
3591         int last_del = 1 + (old_size - 1) / dev->data_bytes_per_chunk;
3592
3593         int start_del = 1 + (new_size + dev->data_bytes_per_chunk - 1) /
3594             dev->data_bytes_per_chunk;
3595         int i;
3596         int chunk_id;
3597
3598         /* Delete backwards so that we don't end up with holes if
3599          * power is lost part-way through the operation.
3600          */
3601         for (i = last_del; i >= start_del; i--) {
3602                 /* NB this could be optimised somewhat,
3603                  * eg. could retrieve the tags and write them without
3604                  * using yaffs_chunk_del
3605                  */
3606
3607                 chunk_id = yaffs_find_del_file_chunk(in, i, NULL);
3608                 if (chunk_id > 0) {
3609                         if (chunk_id <
3610                             (dev->internal_start_block * dev->param.chunks_per_block)
3611                             || chunk_id >=
3612                             ((dev->internal_end_block +
3613                               1) * dev->param.chunks_per_block)) {
3614                                 T(YAFFS_TRACE_ALWAYS,
3615                                   (TSTR("Found daft chunk_id %d for %d" TENDSTR),
3616                                    chunk_id, i));
3617                         } else {
3618                                 in->n_data_chunks--;
3619                                 yaffs_chunk_del(dev, chunk_id, 1, __LINE__);
3620                         }
3621                 }
3622         }
3623
3624 }
3625
3626
3627 void yaffs_resize_file_down( struct yaffs_obj *obj, loff_t new_size)
3628 {
3629         int new_full;
3630         u32 new_partial;
3631         struct yaffs_dev *dev = obj->my_dev;
3632
3633         yaffs_addr_to_chunk(dev, new_size, &new_full, &new_partial);
3634
3635         yaffs_prune_chunks(obj, new_size);
3636
3637         if (new_partial != 0) {
3638                 int last_chunk = 1 + new_full;
3639                 u8 *local_buffer = yaffs_get_temp_buffer(dev, __LINE__);
3640
3641                 /* Got to read and rewrite the last chunk with its new size and zero pad */
3642                 yaffs_rd_data_obj(obj, last_chunk, local_buffer);
3643                 memset(local_buffer + new_partial, 0,
3644                         dev->data_bytes_per_chunk - new_partial);
3645
3646                 yaffs_wr_data_obj(obj, last_chunk, local_buffer,
3647                                              new_partial, 1);
3648
3649                 yaffs_release_temp_buffer(dev, local_buffer, __LINE__);
3650         }
3651
3652         obj->variant.file_variant.file_size = new_size;
3653
3654         yaffs_prune_tree(dev, &obj->variant.file_variant);
3655 }
3656
3657
3658 int yaffs_resize_file(struct yaffs_obj *in, loff_t new_size)
3659 {
3660         struct yaffs_dev *dev = in->my_dev;
3661         int old_size = in->variant.file_variant.file_size;
3662
3663         yaffs_flush_file_cache(in);
3664         yaffs_invalidate_whole_cache(in);
3665
3666         yaffs_check_gc(dev,0);
3667
3668         if (in->variant_type != YAFFS_OBJECT_TYPE_FILE)
3669                 return YAFFS_FAIL;
3670
3671         if (new_size == old_size)
3672                 return YAFFS_OK;
3673                 
3674         if(new_size > old_size){
3675                 yaffs2_handle_hole(in,new_size);
3676                 in->variant.file_variant.file_size = new_size;
3677         } else {
3678                 /* new_size < old_size */ 
3679                 yaffs_resize_file_down(in, new_size);
3680         } 
3681
3682         /* Write a new object header to reflect the resize.
3683          * show we've shrunk the file, if need be
3684          * Do this only if the file is not in the deleted directories
3685          * and is not shadowed.
3686          */
3687         if (in->parent &&
3688             !in->is_shadowed &&
3689             in->parent->obj_id != YAFFS_OBJECTID_UNLINKED &&
3690             in->parent->obj_id != YAFFS_OBJECTID_DELETED)
3691                 yaffs_update_oh(in, NULL, 0, 0, 0, NULL);
3692
3693
3694         return YAFFS_OK;
3695 }
3696
3697
3698 int yaffs_flush_file(struct yaffs_obj *in, int update_time, int data_sync)
3699 {
3700         int ret_val;
3701         if (in->dirty) {
3702                 yaffs_flush_file_cache(in);
3703                 if(data_sync) /* Only sync data */
3704                         ret_val=YAFFS_OK;
3705                 else {
3706                         if (update_time)
3707                                 yaffs_load_current_time(in,0,0);
3708
3709                         ret_val = (yaffs_update_oh(in, NULL, 0, 0, 0, NULL) >=
3710                                 0) ? YAFFS_OK : YAFFS_FAIL;
3711                 }
3712         } else {
3713                 ret_val = YAFFS_OK;
3714         }
3715
3716         return ret_val;
3717
3718 }
3719
3720 static int yaffs_generic_obj_del(struct yaffs_obj *in)
3721 {
3722
3723         /* First off, invalidate the file's data in the cache, without flushing. */
3724         yaffs_invalidate_whole_cache(in);
3725
3726         if (in->my_dev->param.is_yaffs2 && (in->parent != in->my_dev->del_dir)) {
3727                 /* Move to the unlinked directory so we have a record that it was deleted. */
3728                 yaffs_change_obj_name(in, in->my_dev->del_dir, _Y("deleted"), 0, 0);
3729
3730         }
3731
3732         yaffs_remove_obj_from_dir(in);
3733         yaffs_chunk_del(in->my_dev, in->hdr_chunk, 1, __LINE__);
3734         in->hdr_chunk = 0;
3735
3736         yaffs_free_obj(in);
3737         return YAFFS_OK;
3738
3739 }
3740
3741 /* yaffs_del_file deletes the whole file data
3742  * and the inode associated with the file.
3743  * It does not delete the links associated with the file.
3744  */
3745 static int yaffs_unlink_file_if_needed(struct yaffs_obj *in)
3746 {
3747
3748         int ret_val;
3749         int del_now = 0;
3750         struct yaffs_dev *dev = in->my_dev;
3751
3752         if (!in->my_inode)
3753                 del_now = 1;
3754
3755         if (del_now) {
3756                 ret_val =
3757                     yaffs_change_obj_name(in, in->my_dev->del_dir,
3758                                            _Y("deleted"), 0, 0);
3759                 T(YAFFS_TRACE_TRACING,
3760                   (TSTR("yaffs: immediate deletion of file %d" TENDSTR),
3761                    in->obj_id));
3762                 in->deleted = 1;
3763                 in->my_dev->n_deleted_files++;
3764                 if (dev->param.disable_soft_del || dev->param.is_yaffs2)
3765                         yaffs_resize_file(in, 0);
3766                 yaffs_soft_del_file(in);
3767         } else {
3768                 ret_val =
3769                     yaffs_change_obj_name(in, in->my_dev->unlinked_dir,
3770                                            _Y("unlinked"), 0, 0);
3771         }
3772
3773
3774         return ret_val;
3775 }
3776
3777 int yaffs_del_file(struct yaffs_obj *in)
3778 {
3779         int ret_val = YAFFS_OK;
3780         int deleted; /* Need to cache value on stack if in is freed */
3781         struct yaffs_dev *dev = in->my_dev;
3782
3783         if (dev->param.disable_soft_del || dev->param.is_yaffs2)
3784                 yaffs_resize_file(in, 0);
3785
3786         if (in->n_data_chunks > 0) {
3787                 /* Use soft deletion if there is data in the file.
3788                  * That won't be the case if it has been resized to zero.
3789                  */
3790                 if (!in->unlinked)
3791                         ret_val = yaffs_unlink_file_if_needed(in);
3792
3793                 deleted = in->deleted;
3794
3795                 if (ret_val == YAFFS_OK && in->unlinked && !in->deleted) {
3796                         in->deleted = 1;
3797                         deleted = 1;