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