~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/hpfs/dnode.c

Version: ~ [ linux-5.9 ] ~ [ linux-5.8.14 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.70 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.150 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.200 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.238 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.238 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  *  linux/fs/hpfs/dnode.c
  3  *
  4  *  Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
  5  *
  6  *  handling directory dnode tree - adding, deleteing & searching for dirents
  7  */
  8 
  9 #include <linux/buffer_head.h>
 10 #include "hpfs_fn.h"
 11 
 12 static loff_t get_pos(struct dnode *d, struct hpfs_dirent *fde)
 13 {
 14         struct hpfs_dirent *de;
 15         struct hpfs_dirent *de_end = dnode_end_de(d);
 16         int i = 1;
 17         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
 18                 if (de == fde) return ((loff_t) d->self << 4) | (loff_t)i;
 19                 i++;
 20         }
 21         printk("HPFS: get_pos: not_found\n");
 22         return ((loff_t)d->self << 4) | (loff_t)1;
 23 }
 24 
 25 void hpfs_add_pos(struct inode *inode, loff_t *pos)
 26 {
 27         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
 28         int i = 0;
 29         loff_t **ppos;
 30 
 31         if (hpfs_inode->i_rddir_off)
 32                 for (; hpfs_inode->i_rddir_off[i]; i++)
 33                         if (hpfs_inode->i_rddir_off[i] == pos) return;
 34         if (!(i&0x0f)) {
 35                 if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_KERNEL))) {
 36                         printk("HPFS: out of memory for position list\n");
 37                         return;
 38                 }
 39                 if (hpfs_inode->i_rddir_off) {
 40                         memcpy(ppos, hpfs_inode->i_rddir_off, i * sizeof(loff_t));
 41                         kfree(hpfs_inode->i_rddir_off);
 42                 }
 43                 hpfs_inode->i_rddir_off = ppos;
 44         }
 45         hpfs_inode->i_rddir_off[i] = pos;
 46         hpfs_inode->i_rddir_off[i + 1] = NULL;
 47 }
 48 
 49 void hpfs_del_pos(struct inode *inode, loff_t *pos)
 50 {
 51         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
 52         loff_t **i, **j;
 53 
 54         if (!hpfs_inode->i_rddir_off) goto not_f;
 55         for (i = hpfs_inode->i_rddir_off; *i; i++) if (*i == pos) goto fnd;
 56         goto not_f;
 57         fnd:
 58         for (j = i + 1; *j; j++) ;
 59         *i = *(j - 1);
 60         *(j - 1) = NULL;
 61         if (j - 1 == hpfs_inode->i_rddir_off) {
 62                 kfree(hpfs_inode->i_rddir_off);
 63                 hpfs_inode->i_rddir_off = NULL;
 64         }
 65         return;
 66         not_f:
 67         /*printk("HPFS: warning: position pointer %p->%08x not found\n", pos, (int)*pos);*/
 68         return;
 69 }
 70 
 71 static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
 72                          loff_t p1, loff_t p2)
 73 {
 74         struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
 75         loff_t **i;
 76 
 77         if (!hpfs_inode->i_rddir_off) return;
 78         for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
 79         return;
 80 }
 81 
 82 void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
 83 {
 84         if (*p == f) *p = t;
 85 }
 86 
 87 /*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
 88 {
 89         if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
 90 }*/
 91 
 92 void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
 93 {
 94         if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
 95                 int n = (*p & 0x3f) + c;
 96                 if (n > 0x3f) printk("HPFS: hpfs_pos_ins: %08x + %d\n", (int)*p, (int)c >> 8);
 97                 else *p = (*p & ~0x3f) | n;
 98         }
 99 }
100 
101 void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
102 {
103         if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
104                 int n = (*p & 0x3f) - c;
105                 if (n < 1) printk("HPFS: hpfs_pos_ins: %08x - %d\n", (int)*p, (int)c >> 8);
106                 else *p = (*p & ~0x3f) | n;
107         }
108 }
109 
110 static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
111 {
112         struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL;
113         de_end = dnode_end_de(d);
114         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
115                 deee = dee; dee = de;
116         }       
117         return deee;
118 }
119 
120 static struct hpfs_dirent *dnode_last_de(struct dnode *d)
121 {
122         struct hpfs_dirent *de, *de_end, *dee = NULL;
123         de_end = dnode_end_de(d);
124         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
125                 dee = de;
126         }       
127         return dee;
128 }
129 
130 static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
131 {
132         struct hpfs_dirent *de;
133         if (!(de = dnode_last_de(d))) {
134                 hpfs_error(s, "set_last_pointer: empty dnode %08x", d->self);
135                 return;
136         }
137         if (hpfs_sb(s)->sb_chk) {
138                 if (de->down) {
139                         hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
140                                 d->self, de_down_pointer(de));
141                         return;
142                 }
143                 if (de->length != 32) {
144                         hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", d->self);
145                         return;
146                 }
147         }
148         if (ptr) {
149                 if ((d->first_free += 4) > 2048) {
150                         hpfs_error(s,"set_last_pointer: too long dnode %08x", d->self);
151                         d->first_free -= 4;
152                         return;
153                 }
154                 de->length = 36;
155                 de->down = 1;
156                 *(dnode_secno *)((char *)de + 32) = ptr;
157         }
158 }
159 
160 /* Add an entry to dnode and don't care if it grows over 2048 bytes */
161 
162 struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d, unsigned char *name,
163                                 unsigned namelen, secno down_ptr)
164 {
165         struct hpfs_dirent *de;
166         struct hpfs_dirent *de_end = dnode_end_de(d);
167         unsigned d_size = de_size(namelen, down_ptr);
168         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
169                 int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last);
170                 if (!c) {
171                         hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, d->self);
172                         return NULL;
173                 }
174                 if (c < 0) break;
175         }
176         memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
177         memset(de, 0, d_size);
178         if (down_ptr) {
179                 *(int *)((char *)de + d_size - 4) = down_ptr;
180                 de->down = 1;
181         }
182         de->length = d_size;
183         if (down_ptr) de->down = 1;
184         de->not_8x3 = hpfs_is_name_long(name, namelen);
185         de->namelen = namelen;
186         memcpy(de->name, name, namelen);
187         d->first_free += d_size;
188         return de;
189 }
190 
191 /* Delete dirent and don't care about its subtree */
192 
193 void hpfs_delete_de(struct super_block *s, struct dnode *d, struct hpfs_dirent *de)
194 {
195         if (de->last) {
196                 hpfs_error(s, "attempt to delete last dirent in dnode %08x", d->self);
197                 return;
198         }
199         d->first_free -= de->length;
200         memmove(de, de_next_de(de), d->first_free + (char *)d - (char *)de);
201 }
202 
203 static void fix_up_ptrs(struct super_block *s, struct dnode *d)
204 {
205         struct hpfs_dirent *de;
206         struct hpfs_dirent *de_end = dnode_end_de(d);
207         dnode_secno dno = d->self;
208         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de))
209                 if (de->down) {
210                         struct quad_buffer_head qbh;
211                         struct dnode *dd;
212                         if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
213                                 if (dd->up != dno || dd->root_dnode) {
214                                         dd->up = dno;
215                                         dd->root_dnode = 0;
216                                         hpfs_mark_4buffers_dirty(&qbh);
217                                 }
218                                 hpfs_brelse4(&qbh);
219                         }
220                 }
221 }
222 
223 /* Add an entry to dnode and do dnode splitting if required */
224 
225 int hpfs_add_to_dnode(struct inode *i, dnode_secno dno, unsigned char *name, unsigned namelen,
226                       struct hpfs_dirent *new_de, dnode_secno down_ptr)
227 {
228         struct quad_buffer_head qbh, qbh1, qbh2;
229         struct dnode *d, *ad, *rd, *nd = NULL;
230         dnode_secno adno, rdno;
231         struct hpfs_dirent *de;
232         struct hpfs_dirent nde;
233         char *nname;
234         int h;
235         int pos;
236         struct buffer_head *bh;
237         struct fnode *fnode;
238         int c1, c2 = 0;
239         if (!(nname = kmalloc(256, GFP_KERNEL))) {
240                 printk("HPFS: out of memory, can't add to dnode\n");
241                 return 1;
242         }
243         go_up:
244         if (namelen >= 256) {
245                 hpfs_error(i->i_sb, "hpfs_add_to_dnode: namelen == %d", namelen);
246                 if (nd) kfree(nd);
247                 kfree(nname);
248                 return 1;
249         }
250         if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
251                 if (nd) kfree(nd);
252                 kfree(nname);
253                 return 1;
254         }
255         go_up_a:
256         if (hpfs_sb(i->i_sb)->sb_chk)
257                 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
258                         hpfs_brelse4(&qbh);
259                         if (nd) kfree(nd);
260                         kfree(nname);
261                         return 1;
262                 }
263         if (d->first_free + de_size(namelen, down_ptr) <= 2048) {
264                 loff_t t;
265                 copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
266                 t = get_pos(d, de);
267                 for_all_poss(i, hpfs_pos_ins, t, 1);
268                 for_all_poss(i, hpfs_pos_subst, 4, t);
269                 for_all_poss(i, hpfs_pos_subst, 5, t + 1);
270                 hpfs_mark_4buffers_dirty(&qbh);
271                 hpfs_brelse4(&qbh);
272                 if (nd) kfree(nd);
273                 kfree(nname);
274                 return 0;
275         }
276         if (!nd) if (!(nd = kmalloc(0x924, GFP_KERNEL))) {
277                 /* 0x924 is a max size of dnode after adding a dirent with
278                    max name length. We alloc this only once. There must
279                    not be any error while splitting dnodes, otherwise the
280                    whole directory, not only file we're adding, would
281                    be lost. */
282                 printk("HPFS: out of memory for dnode splitting\n");
283                 hpfs_brelse4(&qbh);
284                 kfree(nname);
285                 return 1;
286         }       
287         memcpy(nd, d, d->first_free);
288         copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de);
289         for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1);
290         h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10;
291         if (!(ad = hpfs_alloc_dnode(i->i_sb, d->up, &adno, &qbh1, 0))) {
292                 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
293                 hpfs_brelse4(&qbh);
294                 kfree(nd);
295                 kfree(nname);
296                 return 1;
297         }
298         i->i_size += 2048;
299         i->i_blocks += 4;
300         pos = 1;
301         for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) {
302                 copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de);
303                 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos);
304                 pos++;
305         }
306         copy_de(new_de = &nde, de);
307         memcpy(name = nname, de->name, namelen = de->namelen);
308         for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4);
309         down_ptr = adno;
310         set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
311         de = de_next_de(de);
312         memmove((char *)nd + 20, de, nd->first_free + (char *)nd - (char *)de);
313         nd->first_free -= (char *)de - (char *)nd - 20;
314         memcpy(d, nd, nd->first_free);
315         for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos);
316         fix_up_ptrs(i->i_sb, ad);
317         if (!d->root_dnode) {
318                 dno = ad->up = d->up;
319                 hpfs_mark_4buffers_dirty(&qbh);
320                 hpfs_brelse4(&qbh);
321                 hpfs_mark_4buffers_dirty(&qbh1);
322                 hpfs_brelse4(&qbh1);
323                 goto go_up;
324         }
325         if (!(rd = hpfs_alloc_dnode(i->i_sb, d->up, &rdno, &qbh2, 0))) {
326                 hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
327                 hpfs_brelse4(&qbh);
328                 hpfs_brelse4(&qbh1);
329                 kfree(nd);
330                 kfree(nname);
331                 return 1;
332         }
333         i->i_size += 2048;
334         i->i_blocks += 4;
335         rd->root_dnode = 1;
336         rd->up = d->up;
337         if (!(fnode = hpfs_map_fnode(i->i_sb, d->up, &bh))) {
338                 hpfs_free_dnode(i->i_sb, rdno);
339                 hpfs_brelse4(&qbh);
340                 hpfs_brelse4(&qbh1);
341                 hpfs_brelse4(&qbh2);
342                 kfree(nd);
343                 kfree(nname);
344                 return 1;
345         }
346         fnode->u.external[0].disk_secno = rdno;
347         mark_buffer_dirty(bh);
348         brelse(bh);
349         d->up = ad->up = hpfs_i(i)->i_dno = rdno;
350         d->root_dnode = ad->root_dnode = 0;
351         hpfs_mark_4buffers_dirty(&qbh);
352         hpfs_brelse4(&qbh);
353         hpfs_mark_4buffers_dirty(&qbh1);
354         hpfs_brelse4(&qbh1);
355         qbh = qbh2;
356         set_last_pointer(i->i_sb, rd, dno);
357         dno = rdno;
358         d = rd;
359         goto go_up_a;
360 }
361 
362 /*
363  * Add an entry to directory btree.
364  * I hate such crazy directory structure.
365  * It's easy to read but terrible to write.
366  * I wrote this directory code 4 times.
367  * I hope, now it's finally bug-free.
368  */
369 
370 int hpfs_add_dirent(struct inode *i, unsigned char *name, unsigned namelen,
371                     struct hpfs_dirent *new_de, int cdepth)
372 {
373         struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
374         struct dnode *d;
375         struct hpfs_dirent *de, *de_end;
376         struct quad_buffer_head qbh;
377         dnode_secno dno;
378         int c;
379         int c1, c2 = 0;
380         dno = hpfs_inode->i_dno;
381         down:
382         if (hpfs_sb(i->i_sb)->sb_chk)
383                 if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
384         if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
385         de_end = dnode_end_de(d);
386         for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
387                 if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
388                         hpfs_brelse4(&qbh);
389                         return -1;
390                 }       
391                 if (c < 0) {
392                         if (de->down) {
393                                 dno = de_down_pointer(de);
394                                 hpfs_brelse4(&qbh);
395                                 goto down;
396                         }
397                         break;
398                 }
399         }
400         hpfs_brelse4(&qbh);
401         if (!cdepth) hpfs_lock_creation(i->i_sb);
402         if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
403                 c = 1;
404                 goto ret;
405         }       
406         i->i_version++;
407         c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
408         ret:
409         if (!cdepth) hpfs_unlock_creation(i->i_sb);
410         return c;
411 }
412 
413 /* 
414  * Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
415  * Return the dnode we moved from (to be checked later if it's empty)
416  */
417 
418 static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
419 {
420         dnode_secno dno, ddno;
421         dnode_secno chk_up = to;
422         struct dnode *dnode;
423         struct quad_buffer_head qbh;
424         struct hpfs_dirent *de, *nde;
425         int a;
426         loff_t t;
427         int c1, c2 = 0;
428         dno = from;
429         while (1) {
430                 if (hpfs_sb(i->i_sb)->sb_chk)
431                         if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
432                                 return 0;
433                 if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0;
434                 if (hpfs_sb(i->i_sb)->sb_chk) {
435                         if (dnode->up != chk_up) {
436                                 hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x",
437                                         dno, chk_up, dnode->up);
438                                 hpfs_brelse4(&qbh);
439                                 return 0;
440                         }
441                         chk_up = dno;
442                 }
443                 if (!(de = dnode_last_de(dnode))) {
444                         hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
445                         hpfs_brelse4(&qbh);
446                         return 0;
447                 }
448                 if (!de->down) break;
449                 dno = de_down_pointer(de);
450                 hpfs_brelse4(&qbh);
451         }
452         while (!(de = dnode_pre_last_de(dnode))) {
453                 dnode_secno up = dnode->up;
454                 hpfs_brelse4(&qbh);
455                 hpfs_free_dnode(i->i_sb, dno);
456                 i->i_size -= 2048;
457                 i->i_blocks -= 4;
458                 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5);
459                 if (up == to) return to;
460                 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0;
461                 if (dnode->root_dnode) {
462                         hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to);
463                         hpfs_brelse4(&qbh);
464                         return 0;
465                 }
466                 de = dnode_last_de(dnode);
467                 if (!de || !de->down) {
468                         hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno);
469                         hpfs_brelse4(&qbh);
470                         return 0;
471                 }
472                 dnode->first_free -= 4;
473                 de->length -= 4;
474                 de->down = 0;
475                 hpfs_mark_4buffers_dirty(&qbh);
476                 dno = up;
477         }
478         t = get_pos(dnode, de);
479         for_all_poss(i, hpfs_pos_subst, t, 4);
480         for_all_poss(i, hpfs_pos_subst, t + 1, 5);
481         if (!(nde = kmalloc(de->length, GFP_KERNEL))) {
482                 hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted");
483                 hpfs_brelse4(&qbh);
484                 return 0;
485         }
486         memcpy(nde, de, de->length);
487         ddno = de->down ? de_down_pointer(de) : 0;
488         hpfs_delete_de(i->i_sb, dnode, de);
489         set_last_pointer(i->i_sb, dnode, ddno);
490         hpfs_mark_4buffers_dirty(&qbh);
491         hpfs_brelse4(&qbh);
492         a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
493         kfree(nde);
494         if (a) return 0;
495         return dno;
496 }
497 
498 /* 
499  * Check if a dnode is empty and delete it from the tree
500  * (chkdsk doesn't like empty dnodes)
501  */
502 
503 static void delete_empty_dnode(struct inode *i, dnode_secno dno)
504 {
505         struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
506         struct quad_buffer_head qbh;
507         struct dnode *dnode;
508         dnode_secno down, up, ndown;
509         int p;
510         struct hpfs_dirent *de;
511         int c1, c2 = 0;
512         try_it_again:
513         if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return;
514         if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return;
515         if (dnode->first_free > 56) goto end;
516         if (dnode->first_free == 52 || dnode->first_free == 56) {
517                 struct hpfs_dirent *de_end;
518                 int root = dnode->root_dnode;
519                 up = dnode->up;
520                 de = dnode_first_de(dnode);
521                 down = de->down ? de_down_pointer(de) : 0;
522                 if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) {
523                         hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno);
524                         goto end;
525                 }
526                 hpfs_brelse4(&qbh);
527                 hpfs_free_dnode(i->i_sb, dno);
528                 i->i_size -= 2048;
529                 i->i_blocks -= 4;
530                 if (root) {
531                         struct fnode *fnode;
532                         struct buffer_head *bh;
533                         struct dnode *d1;
534                         struct quad_buffer_head qbh1;
535                         if (hpfs_sb(i->i_sb)->sb_chk) if (up != i->i_ino) {
536                                 hpfs_error(i->i_sb, "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08x", dno, up, i->i_ino);
537                                 return;
538                         }
539                         if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
540                                 d1->up = up;
541                                 d1->root_dnode = 1;
542                                 hpfs_mark_4buffers_dirty(&qbh1);
543                                 hpfs_brelse4(&qbh1);
544                         }
545                         if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
546                                 fnode->u.external[0].disk_secno = down;
547                                 mark_buffer_dirty(bh);
548                                 brelse(bh);
549                         }
550                         hpfs_inode->i_dno = down;
551                         for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
552                         return;
553                 }
554                 if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
555                 p = 1;
556                 de_end = dnode_end_de(dnode);
557                 for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
558                         if (de->down) if (de_down_pointer(de) == dno) goto fnd;
559                 hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
560                 goto end;
561                 fnd:
562                 for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
563                 if (!down) {
564                         de->down = 0;
565                         de->length -= 4;
566                         dnode->first_free -= 4;
567                         memmove(de_next_de(de), (char *)de_next_de(de) + 4,
568                                 (char *)dnode + dnode->first_free - (char *)de_next_de(de));
569                 } else {
570                         struct dnode *d1;
571                         struct quad_buffer_head qbh1;
572                         *(dnode_secno *) ((void *) de + de->length - 4) = down;
573                         if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
574                                 d1->up = up;
575                                 hpfs_mark_4buffers_dirty(&qbh1);
576                                 hpfs_brelse4(&qbh1);
577                         }
578                 }
579         } else {
580                 hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, dnode->first_free);
581                 goto end;
582         }
583 
584         if (!de->last) {
585                 struct hpfs_dirent *de_next = de_next_de(de);
586                 struct hpfs_dirent *de_cp;
587                 struct dnode *d1;
588                 struct quad_buffer_head qbh1;
589                 if (!de_next->down) goto endm;
590                 ndown = de_down_pointer(de_next);
591                 if (!(de_cp = kmalloc(de->length, GFP_KERNEL))) {
592                         printk("HPFS: out of memory for dtree balancing\n");
593                         goto endm;
594                 }
595                 memcpy(de_cp, de, de->length);
596                 hpfs_delete_de(i->i_sb, dnode, de);
597                 hpfs_mark_4buffers_dirty(&qbh);
598                 hpfs_brelse4(&qbh);
599                 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
600                 for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
601                 if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
602                         d1->up = ndown;
603                         hpfs_mark_4buffers_dirty(&qbh1);
604                         hpfs_brelse4(&qbh1);
605                 }
606                 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
607                 /*printk("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", up, ndown, down, dno);*/
608                 dno = up;
609                 kfree(de_cp);
610                 goto try_it_again;
611         } else {
612                 struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
613                 struct hpfs_dirent *de_cp;
614                 struct dnode *d1;
615                 struct quad_buffer_head qbh1;
616                 dnode_secno dlp;
617                 if (!de_prev) {
618                         hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
619                         hpfs_mark_4buffers_dirty(&qbh);
620                         hpfs_brelse4(&qbh);
621                         dno = up;
622                         goto try_it_again;
623                 }
624                 if (!de_prev->down) goto endm;
625                 ndown = de_down_pointer(de_prev);
626                 if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
627                         struct hpfs_dirent *del = dnode_last_de(d1);
628                         dlp = del->down ? de_down_pointer(del) : 0;
629                         if (!dlp && down) {
630                                 if (d1->first_free > 2044) {
631                                         if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
632                                                 printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
633                                                 printk("HPFS: warning: terminating balancing operation\n");
634                                         }
635                                         hpfs_brelse4(&qbh1);
636                                         goto endm;
637                                 }
638                                 if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
639                                         printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
640                                         printk("HPFS: warning: goin'on\n");
641                                 }
642                                 del->length += 4;
643                                 del->down = 1;
644                                 d1->first_free += 4;
645                         }
646                         if (dlp && !down) {
647                                 del->length -= 4;
648                                 del->down = 0;
649                                 d1->first_free -= 4;
650                         } else if (down)
651                                 *(dnode_secno *) ((void *) del + del->length - 4) = down;
652                 } else goto endm;
653                 if (!(de_cp = kmalloc(de_prev->length, GFP_KERNEL))) {
654                         printk("HPFS: out of memory for dtree balancing\n");
655                         hpfs_brelse4(&qbh1);
656                         goto endm;
657                 }
658                 hpfs_mark_4buffers_dirty(&qbh1);
659                 hpfs_brelse4(&qbh1);
660                 memcpy(de_cp, de_prev, de_prev->length);
661                 hpfs_delete_de(i->i_sb, dnode, de_prev);
662                 if (!de_prev->down) {
663                         de_prev->length += 4;
664                         de_prev->down = 1;
665                         dnode->first_free += 4;
666                 }
667                 *(dnode_secno *) ((void *) de_prev + de_prev->length - 4) = ndown;
668                 hpfs_mark_4buffers_dirty(&qbh);
669                 hpfs_brelse4(&qbh);
670                 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
671                 for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
672                 if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
673                         d1->up = ndown;
674                         hpfs_mark_4buffers_dirty(&qbh1);
675                         hpfs_brelse4(&qbh1);
676                 }
677                 hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
678                 dno = up;
679                 kfree(de_cp);
680                 goto try_it_again;
681         }
682         endm:
683         hpfs_mark_4buffers_dirty(&qbh);
684         end:
685         hpfs_brelse4(&qbh);
686 }
687 
688 
689 /* Delete dirent from directory */
690 
691 int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
692                        struct quad_buffer_head *qbh, int depth)
693 {
694         struct dnode *dnode = qbh->data;
695         dnode_secno down = 0;
696         int lock = 0;
697         loff_t t;
698         if (de->first || de->last) {
699                 hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
700                 hpfs_brelse4(qbh);
701                 return 1;
702         }
703         if (de->down) down = de_down_pointer(de);
704         if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
705                 lock = 1;
706                 hpfs_lock_creation(i->i_sb);
707                 if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
708                         hpfs_brelse4(qbh);
709                         hpfs_unlock_creation(i->i_sb);
710                         return 2;
711                 }
712         }
713         i->i_version++;
714         for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
715         hpfs_delete_de(i->i_sb, dnode, de);
716         hpfs_mark_4buffers_dirty(qbh);
717         hpfs_brelse4(qbh);
718         if (down) {
719                 dnode_secno a = move_to_top(i, down, dno);
720                 for_all_poss(i, hpfs_pos_subst, 5, t);
721                 if (a) delete_empty_dnode(i, a);
722                 if (lock) hpfs_unlock_creation(i->i_sb);
723                 return !a;
724         }
725         delete_empty_dnode(i, dno);
726         if (lock) hpfs_unlock_creation(i->i_sb);
727         return 0;
728 }
729 
730 void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
731                        int *n_subdirs, int *n_items)
732 {
733         struct dnode *dnode;
734         struct quad_buffer_head qbh;
735         struct hpfs_dirent *de;
736         dnode_secno ptr, odno = 0;
737         int c1, c2 = 0;
738         int d1, d2 = 0;
739         go_down:
740         if (n_dnodes) (*n_dnodes)++;
741         if (hpfs_sb(s)->sb_chk)
742                 if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
743         ptr = 0;
744         go_up:
745         if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
746         if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && dnode->up != odno)
747                 hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, dnode->up);
748         de = dnode_first_de(dnode);
749         if (ptr) while(1) {
750                 if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
751                 if (de->last) {
752                         hpfs_brelse4(&qbh);
753                         hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
754                                 ptr, dno, odno);
755                         return;
756                 }
757                 de = de_next_de(de);
758         }
759         next_de:
760         if (de->down) {
761                 odno = dno;
762                 dno = de_down_pointer(de);
763                 hpfs_brelse4(&qbh);
764                 goto go_down;
765         }
766         process_de:
767         if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
768         if (!de->first && !de->last && n_items) (*n_items)++;
769         if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
770         ptr = dno;
771         dno = dnode->up;
772         if (dnode->root_dnode) {
773                 hpfs_brelse4(&qbh);
774                 return;
775         }
776         hpfs_brelse4(&qbh);
777         if (hpfs_sb(s)->sb_chk)
778                 if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
779         odno = -1;
780         goto go_up;
781 }
782 
783 static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
784                                           struct quad_buffer_head *qbh, struct dnode **dn)
785 {
786         int i;
787         struct hpfs_dirent *de, *de_end;
788         struct dnode *dnode;
789         dnode = hpfs_map_dnode(s, dno, qbh);
790         if (!dnode) return NULL;
791         if (dn) *dn=dnode;
792         de = dnode_first_de(dnode);
793         de_end = dnode_end_de(dnode);
794         for (i = 1; de < de_end; i++, de = de_next_de(de)) {
795                 if (i == n) {
796                         return de;
797                 }       
798                 if (de->last) break;
799         }
800         hpfs_brelse4(qbh);
801         hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
802         return NULL;
803 }
804 
805 dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
806 {
807         struct quad_buffer_head qbh;
808         dnode_secno d = dno;
809         dnode_secno up = 0;
810         struct hpfs_dirent *de;
811         int c1, c2 = 0;
812 
813         again:
814         if (hpfs_sb(s)->sb_chk)
815                 if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
816                         return d;
817         if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
818         if (hpfs_sb(s)->sb_chk)
819                 if (up && ((struct dnode *)qbh.data)->up != up)
820                         hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, ((struct dnode *)qbh.data)->up);
821         if (!de->down) {
822                 hpfs_brelse4(&qbh);
823                 return d;
824         }
825         up = d;
826         d = de_down_pointer(de);
827         hpfs_brelse4(&qbh);
828         goto again;
829 }
830 
831 struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
832                                    struct quad_buffer_head *qbh)
833 {
834         loff_t pos;
835         unsigned c;
836         dnode_secno dno;
837         struct hpfs_dirent *de, *d;
838         struct hpfs_dirent *up_de;
839         struct hpfs_dirent *end_up_de;
840         struct dnode *dnode;
841         struct dnode *up_dnode;
842         struct quad_buffer_head qbh0;
843 
844         pos = *posp;
845         dno = pos >> 6 << 2;
846         pos &= 077;
847         if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
848                 goto bail;
849 
850         /* Going to the next dirent */
851         if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
852                 if (!(++*posp & 077)) {
853                         hpfs_error(inode->i_sb, "map_pos_dirent: pos crossed dnode boundary; pos = %08x", *posp);
854                         goto bail;
855                 }
856                 /* We're going down the tree */
857                 if (d->down) {
858                         *posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
859                 }
860         
861                 return de;
862         }
863 
864         /* Going up */
865         if (dnode->root_dnode) goto bail;
866 
867         if (!(up_dnode = hpfs_map_dnode(inode->i_sb, dnode->up, &qbh0)))
868                 goto bail;
869 
870         end_up_de = dnode_end_de(up_dnode);
871         c = 0;
872         for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
873              up_de = de_next_de(up_de)) {
874                 if (!(++c & 077)) hpfs_error(inode->i_sb,
875                         "map_pos_dirent: pos crossed dnode boundary; dnode = %08x", dnode->up);
876                 if (up_de->down && de_down_pointer(up_de) == dno) {
877                         *posp = ((loff_t) dnode->up << 4) + c;
878                         hpfs_brelse4(&qbh0);
879                         return de;
880                 }
881         }
882         
883         hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
884                 dno, dnode->up);
885         hpfs_brelse4(&qbh0);
886         
887         bail:
888         *posp = 12;
889         return de;
890 }
891 
892 /* Find a dirent in tree */
893 
894 struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno, char *name, unsigned len,
895                                dnode_secno *dd, struct quad_buffer_head *qbh)
896 {
897         struct dnode *dnode;
898         struct hpfs_dirent *de;
899         struct hpfs_dirent *de_end;
900         int c1, c2 = 0;
901 
902         if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
903         again:
904         if (hpfs_sb(inode->i_sb)->sb_chk)
905                 if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
906         if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
907         
908         de_end = dnode_end_de(dnode);
909         for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
910                 int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
911                 if (!t) {
912                         if (dd) *dd = dno;
913                         return de;
914                 }
915                 if (t < 0) {
916                         if (de->down) {
917                                 dno = de_down_pointer(de);
918                                 hpfs_brelse4(qbh);
919                                 goto again;
920                         }
921                 break;
922                 }
923         }
924         hpfs_brelse4(qbh);
925         return NULL;
926 }
927 
928 /*
929  * Remove empty directory. In normal cases it is only one dnode with two
930  * entries, but we must handle also such obscure cases when it's a tree
931  * of empty dnodes.
932  */
933 
934 void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
935 {
936         struct quad_buffer_head qbh;
937         struct dnode *dnode;
938         struct hpfs_dirent *de;
939         dnode_secno d1, d2, rdno = dno;
940         while (1) {
941                 if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
942                 de = dnode_first_de(dnode);
943                 if (de->last) {
944                         if (de->down) d1 = de_down_pointer(de);
945                         else goto error;
946                         hpfs_brelse4(&qbh);
947                         hpfs_free_dnode(s, dno);
948                         dno = d1;
949                 } else break;
950         }
951         if (!de->first) goto error;
952         d1 = de->down ? de_down_pointer(de) : 0;
953         de = de_next_de(de);
954         if (!de->last) goto error;
955         d2 = de->down ? de_down_pointer(de) : 0;
956         hpfs_brelse4(&qbh);
957         hpfs_free_dnode(s, dno);
958         do {
959                 while (d1) {
960                         if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
961                         de = dnode_first_de(dnode);
962                         if (!de->last) goto error;
963                         d1 = de->down ? de_down_pointer(de) : 0;
964                         hpfs_brelse4(&qbh);
965                         hpfs_free_dnode(s, dno);
966                 }
967                 d1 = d2;
968                 d2 = 0;
969         } while (d1);
970         return;
971         error:
972         hpfs_brelse4(&qbh);
973         hpfs_free_dnode(s, dno);
974         hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
975 }
976 
977 /* 
978  * Find dirent for specified fnode. Use truncated 15-char name in fnode as
979  * a help for searching.
980  */
981 
982 struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
983                                      struct fnode *f, struct quad_buffer_head *qbh)
984 {
985         char *name1;
986         char *name2;
987         int name1len, name2len;
988         struct dnode *d;
989         dnode_secno dno, downd;
990         struct fnode *upf;
991         struct buffer_head *bh;
992         struct hpfs_dirent *de, *de_end;
993         int c;
994         int c1, c2 = 0;
995         int d1, d2 = 0;
996         name1 = f->name;
997         if (!(name2 = kmalloc(256, GFP_KERNEL))) {
998                 printk("HPFS: out of memory, can't map dirent\n");
999                 return NULL;
1000         }
1001         if (f->len <= 15)
1002                 memcpy(name2, name1, name1len = name2len = f->len);
1003         else {
1004                 memcpy(name2, name1, 15);
1005                 memset(name2 + 15, 0xff, 256 - 15);
1006                 /*name2[15] = 0xff;*/
1007                 name1len = 15; name2len = 256;
1008         }
1009         if (!(upf = hpfs_map_fnode(s, f->up, &bh))) {
1010                 kfree(name2);
1011                 return NULL;
1012         }       
1013         if (!upf->dirflag) {
1014                 brelse(bh);
1015                 hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, f->up);
1016                 kfree(name2);
1017                 return NULL;
1018         }
1019         dno = upf->u.external[0].disk_secno;
1020         brelse(bh);
1021         go_down:
1022         downd = 0;
1023         go_up:
1024         if (!(d = hpfs_map_dnode(s, dno, qbh))) {
1025                 kfree(name2);
1026                 return NULL;
1027         }
1028         de_end = dnode_end_de(d);
1029         de = dnode_first_de(d);
1030         if (downd) {
1031                 while (de < de_end) {
1032                         if (de->down) if (de_down_pointer(de) == downd) goto f;
1033                         de = de_next_de(de);
1034                 }
1035                 hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
1036                 hpfs_brelse4(qbh);
1037                 kfree(name2);
1038                 return NULL;
1039         }
1040         next_de:
1041         if (de->fnode == fno) {
1042                 kfree(name2);
1043                 return de;
1044         }
1045         c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
1046         if (c < 0 && de->down) {
1047                 dno = de_down_pointer(de);
1048                 hpfs_brelse4(qbh);
1049                 if (hpfs_sb(s)->sb_chk)
1050                         if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
1051                         kfree(name2);
1052                         return NULL;
1053                 }
1054                 goto go_down;
1055         }
1056         f:
1057         if (de->fnode == fno) {
1058                 kfree(name2);
1059                 return de;
1060         }
1061         c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
1062         if (c < 0 && !de->last) goto not_found;
1063         if ((de = de_next_de(de)) < de_end) goto next_de;
1064         if (d->root_dnode) goto not_found;
1065         downd = dno;
1066         dno = d->up;
1067         hpfs_brelse4(qbh);
1068         if (hpfs_sb(s)->sb_chk)
1069                 if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
1070                         kfree(name2);
1071                         return NULL;
1072                 }
1073         goto go_up;
1074         not_found:
1075         hpfs_brelse4(qbh);
1076         hpfs_error(s, "dirent for fnode %08x not found", fno);
1077         kfree(name2);
1078         return NULL;
1079 }
1080 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp