1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103#include <linux/fs.h>
104#include <linux/quotaops.h>
105#include <linux/slab.h>
106#include "jfs_incore.h"
107#include "jfs_superblock.h"
108#include "jfs_filsys.h"
109#include "jfs_metapage.h"
110#include "jfs_dmap.h"
111#include "jfs_unicode.h"
112#include "jfs_debug.h"
113
114
115struct dtsplit {
116 struct metapage *mp;
117 s16 index;
118 s16 nslot;
119 struct component_name *key;
120 ddata_t *data;
121 struct pxdlist *pxdlist;
122};
123
124#define DT_PAGE(IP, MP) BT_PAGE(IP, MP, dtpage_t, i_dtroot)
125
126
127#define DT_GETPAGE(IP, BN, MP, SIZE, P, RC) \
128do { \
129 BT_GETPAGE(IP, BN, MP, dtpage_t, SIZE, P, RC, i_dtroot); \
130 if (!(RC)) { \
131 if (((P)->header.nextindex > \
132 (((BN) == 0) ? DTROOTMAXSLOT : (P)->header.maxslot)) || \
133 ((BN) && ((P)->header.maxslot > DTPAGEMAXSLOT))) { \
134 BT_PUTPAGE(MP); \
135 jfs_error((IP)->i_sb, \
136 "DT_GETPAGE: dtree page corrupt\n"); \
137 MP = NULL; \
138 RC = -EIO; \
139 } \
140 } \
141} while (0)
142
143
144#define DT_PUTPAGE(MP) BT_PUTPAGE(MP)
145
146#define DT_GETSEARCH(IP, LEAF, BN, MP, P, INDEX) \
147 BT_GETSEARCH(IP, LEAF, BN, MP, dtpage_t, P, INDEX, i_dtroot)
148
149
150
151
152static int dtSplitUp(tid_t tid, struct inode *ip,
153 struct dtsplit * split, struct btstack * btstack);
154
155static int dtSplitPage(tid_t tid, struct inode *ip, struct dtsplit * split,
156 struct metapage ** rmpp, dtpage_t ** rpp, pxd_t * rxdp);
157
158static int dtExtendPage(tid_t tid, struct inode *ip,
159 struct dtsplit * split, struct btstack * btstack);
160
161static int dtSplitRoot(tid_t tid, struct inode *ip,
162 struct dtsplit * split, struct metapage ** rmpp);
163
164static int dtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
165 dtpage_t * fp, struct btstack * btstack);
166
167static int dtRelink(tid_t tid, struct inode *ip, dtpage_t * p);
168
169static int dtReadFirst(struct inode *ip, struct btstack * btstack);
170
171static int dtReadNext(struct inode *ip,
172 loff_t * offset, struct btstack * btstack);
173
174static int dtCompare(struct component_name * key, dtpage_t * p, int si);
175
176static int ciCompare(struct component_name * key, dtpage_t * p, int si,
177 int flag);
178
179static void dtGetKey(dtpage_t * p, int i, struct component_name * key,
180 int flag);
181
182static int ciGetLeafPrefixKey(dtpage_t * lp, int li, dtpage_t * rp,
183 int ri, struct component_name * key, int flag);
184
185static void dtInsertEntry(dtpage_t * p, int index, struct component_name * key,
186 ddata_t * data, struct dt_lock **);
187
188static void dtMoveEntry(dtpage_t * sp, int si, dtpage_t * dp,
189 struct dt_lock ** sdtlock, struct dt_lock ** ddtlock,
190 int do_index);
191
192static void dtDeleteEntry(dtpage_t * p, int fi, struct dt_lock ** dtlock);
193
194static void dtTruncateEntry(dtpage_t * p, int ti, struct dt_lock ** dtlock);
195
196static void dtLinelockFreelist(dtpage_t * p, int m, struct dt_lock ** dtlock);
197
198#define ciToUpper(c) UniStrupr((c)->name)
199
200
201
202
203
204
205
206
207
208static struct metapage *read_index_page(struct inode *inode, s64 blkno)
209{
210 int rc;
211 s64 xaddr;
212 int xflag;
213 s32 xlen;
214
215 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1);
216 if (rc || (xaddr == 0))
217 return NULL;
218
219 return read_metapage(inode, xaddr, PSIZE, 1);
220}
221
222
223
224
225
226
227static struct metapage *get_index_page(struct inode *inode, s64 blkno)
228{
229 int rc;
230 s64 xaddr;
231 int xflag;
232 s32 xlen;
233
234 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1);
235 if (rc || (xaddr == 0))
236 return NULL;
237
238 return get_metapage(inode, xaddr, PSIZE, 1);
239}
240
241
242
243
244
245
246
247
248
249static struct dir_table_slot *find_index(struct inode *ip, u32 index,
250 struct metapage ** mp, s64 *lblock)
251{
252 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
253 s64 blkno;
254 s64 offset;
255 int page_offset;
256 struct dir_table_slot *slot;
257 static int maxWarnings = 10;
258
259 if (index < 2) {
260 if (maxWarnings) {
261 jfs_warn("find_entry called with index = %d", index);
262 maxWarnings--;
263 }
264 return NULL;
265 }
266
267 if (index >= jfs_ip->next_index) {
268 jfs_warn("find_entry called with index >= next_index");
269 return NULL;
270 }
271
272 if (jfs_dirtable_inline(ip)) {
273
274
275
276 *mp = NULL;
277 slot = &jfs_ip->i_dirtable[index - 2];
278 } else {
279 offset = (index - 2) * sizeof(struct dir_table_slot);
280 page_offset = offset & (PSIZE - 1);
281 blkno = ((offset + 1) >> L2PSIZE) <<
282 JFS_SBI(ip->i_sb)->l2nbperpage;
283
284 if (*mp && (*lblock != blkno)) {
285 release_metapage(*mp);
286 *mp = NULL;
287 }
288 if (!(*mp)) {
289 *lblock = blkno;
290 *mp = read_index_page(ip, blkno);
291 }
292 if (!(*mp)) {
293 jfs_err("free_index: error reading directory table");
294 return NULL;
295 }
296
297 slot =
298 (struct dir_table_slot *) ((char *) (*mp)->data +
299 page_offset);
300 }
301 return slot;
302}
303
304static inline void lock_index(tid_t tid, struct inode *ip, struct metapage * mp,
305 u32 index)
306{
307 struct tlock *tlck;
308 struct linelock *llck;
309 struct lv *lv;
310
311 tlck = txLock(tid, ip, mp, tlckDATA);
312 llck = (struct linelock *) tlck->lock;
313
314 if (llck->index >= llck->maxcnt)
315 llck = txLinelock(llck);
316 lv = &llck->lv[llck->index];
317
318
319
320
321
322 lv->offset = ((index - 2) & 511) >> 1;
323 lv->length = 1;
324 llck->index++;
325}
326
327
328
329
330
331
332
333
334static u32 add_index(tid_t tid, struct inode *ip, s64 bn, int slot)
335{
336 struct super_block *sb = ip->i_sb;
337 struct jfs_sb_info *sbi = JFS_SBI(sb);
338 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
339 u64 blkno;
340 struct dir_table_slot *dirtab_slot;
341 u32 index;
342 struct linelock *llck;
343 struct lv *lv;
344 struct metapage *mp;
345 s64 offset;
346 uint page_offset;
347 struct tlock *tlck;
348 s64 xaddr;
349
350 ASSERT(DO_INDEX(ip));
351
352 if (jfs_ip->next_index < 2) {
353 jfs_warn("add_index: next_index = %d. Resetting!",
354 jfs_ip->next_index);
355 jfs_ip->next_index = 2;
356 }
357
358 index = jfs_ip->next_index++;
359
360 if (index <= MAX_INLINE_DIRTABLE_ENTRY) {
361
362
363
364 ip->i_size = (loff_t) (index - 1) << 3;
365
366
367
368
369 dirtab_slot = &jfs_ip->i_dirtable[index-2];
370 dirtab_slot->flag = DIR_INDEX_VALID;
371 dirtab_slot->slot = slot;
372 DTSaddress(dirtab_slot, bn);
373
374 set_cflag(COMMIT_Dirtable, ip);
375
376 return index;
377 }
378 if (index == (MAX_INLINE_DIRTABLE_ENTRY + 1)) {
379 struct dir_table_slot temp_table[12];
380
381
382
383
384
385 if (dquot_alloc_block(ip, sbi->nbperpage))
386 goto clean_up;
387 if (dbAlloc(ip, 0, sbi->nbperpage, &xaddr)) {
388 dquot_free_block(ip, sbi->nbperpage);
389 goto clean_up;
390 }
391
392
393
394
395
396 memcpy(temp_table, &jfs_ip->i_dirtable, sizeof(temp_table));
397
398
399
400
401 xtInitRoot(tid, ip);
402
403
404
405
406 if (xtInsert(tid, ip, 0, 0, sbi->nbperpage, &xaddr, 0)) {
407
408 jfs_warn("add_index: xtInsert failed!");
409 memcpy(&jfs_ip->i_dirtable, temp_table,
410 sizeof (temp_table));
411 dbFree(ip, xaddr, sbi->nbperpage);
412 dquot_free_block(ip, sbi->nbperpage);
413 goto clean_up;
414 }
415 ip->i_size = PSIZE;
416
417 mp = get_index_page(ip, 0);
418 if (!mp) {
419 jfs_err("add_index: get_metapage failed!");
420 xtTruncate(tid, ip, 0, COMMIT_PWMAP);
421 memcpy(&jfs_ip->i_dirtable, temp_table,
422 sizeof (temp_table));
423 goto clean_up;
424 }
425 tlck = txLock(tid, ip, mp, tlckDATA);
426 llck = (struct linelock *) & tlck->lock;
427 ASSERT(llck->index == 0);
428 lv = &llck->lv[0];
429
430 lv->offset = 0;
431 lv->length = 6;
432 llck->index++;
433
434 memcpy(mp->data, temp_table, sizeof(temp_table));
435
436 mark_metapage_dirty(mp);
437 release_metapage(mp);
438
439
440
441
442 clear_cflag(COMMIT_Dirtable, ip);
443 }
444
445 offset = (index - 2) * sizeof(struct dir_table_slot);
446 page_offset = offset & (PSIZE - 1);
447 blkno = ((offset + 1) >> L2PSIZE) << sbi->l2nbperpage;
448 if (page_offset == 0) {
449
450
451
452 xaddr = 0;
453 if (xtInsert(tid, ip, 0, blkno, sbi->nbperpage, &xaddr, 0)) {
454 jfs_warn("add_index: xtInsert failed!");
455 goto clean_up;
456 }
457 ip->i_size += PSIZE;
458
459 if ((mp = get_index_page(ip, blkno)))
460 memset(mp->data, 0, PSIZE);
461 else
462 xtTruncate(tid, ip, offset, COMMIT_PWMAP);
463 } else
464 mp = read_index_page(ip, blkno);
465
466 if (!mp) {
467 jfs_err("add_index: get/read_metapage failed!");
468 goto clean_up;
469 }
470
471 lock_index(tid, ip, mp, index);
472
473 dirtab_slot =
474 (struct dir_table_slot *) ((char *) mp->data + page_offset);
475 dirtab_slot->flag = DIR_INDEX_VALID;
476 dirtab_slot->slot = slot;
477 DTSaddress(dirtab_slot, bn);
478
479 mark_metapage_dirty(mp);
480 release_metapage(mp);
481
482 return index;
483
484 clean_up:
485
486 jfs_ip->next_index--;
487
488 return 0;
489}
490
491
492
493
494
495
496static void free_index(tid_t tid, struct inode *ip, u32 index, u32 next)
497{
498 struct dir_table_slot *dirtab_slot;
499 s64 lblock;
500 struct metapage *mp = NULL;
501
502 dirtab_slot = find_index(ip, index, &mp, &lblock);
503
504 if (!dirtab_slot)
505 return;
506
507 dirtab_slot->flag = DIR_INDEX_FREE;
508 dirtab_slot->slot = dirtab_slot->addr1 = 0;
509 dirtab_slot->addr2 = cpu_to_le32(next);
510
511 if (mp) {
512 lock_index(tid, ip, mp, index);
513 mark_metapage_dirty(mp);
514 release_metapage(mp);
515 } else
516 set_cflag(COMMIT_Dirtable, ip);
517}
518
519
520
521
522
523
524static void modify_index(tid_t tid, struct inode *ip, u32 index, s64 bn,
525 int slot, struct metapage ** mp, s64 *lblock)
526{
527 struct dir_table_slot *dirtab_slot;
528
529 dirtab_slot = find_index(ip, index, mp, lblock);
530
531 if (!dirtab_slot)
532 return;
533
534 DTSaddress(dirtab_slot, bn);
535 dirtab_slot->slot = slot;
536
537 if (*mp) {
538 lock_index(tid, ip, *mp, index);
539 mark_metapage_dirty(*mp);
540 } else
541 set_cflag(COMMIT_Dirtable, ip);
542}
543
544
545
546
547
548
549static int read_index(struct inode *ip, u32 index,
550 struct dir_table_slot * dirtab_slot)
551{
552 s64 lblock;
553 struct metapage *mp = NULL;
554 struct dir_table_slot *slot;
555
556 slot = find_index(ip, index, &mp, &lblock);
557 if (!slot) {
558 return -EIO;
559 }
560
561 memcpy(dirtab_slot, slot, sizeof(struct dir_table_slot));
562
563 if (mp)
564 release_metapage(mp);
565
566 return 0;
567}
568
569
570
571
572
573
574
575
576
577
578
579
580int dtSearch(struct inode *ip, struct component_name * key, ino_t * data,
581 struct btstack * btstack, int flag)
582{
583 int rc = 0;
584 int cmp = 1;
585 s64 bn;
586 struct metapage *mp;
587 dtpage_t *p;
588 s8 *stbl;
589 int base, index, lim;
590 struct btframe *btsp;
591 pxd_t *pxd;
592 int psize = 288;
593 ino_t inumber;
594 struct component_name ciKey;
595 struct super_block *sb = ip->i_sb;
596
597 ciKey.name = kmalloc_array(JFS_NAME_MAX + 1, sizeof(wchar_t),
598 GFP_NOFS);
599 if (!ciKey.name) {
600 rc = -ENOMEM;
601 goto dtSearch_Exit2;
602 }
603
604
605
606 UniStrcpy(ciKey.name, key->name);
607 ciKey.namlen = key->namlen;
608
609
610 if ((JFS_SBI(sb)->mntflag & JFS_OS2) == JFS_OS2) {
611 ciToUpper(&ciKey);
612 }
613 BT_CLR(btstack);
614
615
616 btstack->nsplit = 1;
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634 for (bn = 0;;) {
635
636 DT_GETPAGE(ip, bn, mp, psize, p, rc);
637 if (rc)
638 goto dtSearch_Exit1;
639
640
641 stbl = DT_GETSTBL(p);
642
643
644
645
646 for (base = 0, lim = p->header.nextindex; lim; lim >>= 1) {
647 index = base + (lim >> 1);
648
649 if (p->header.flag & BT_LEAF) {
650
651 cmp =
652 ciCompare(&ciKey, p, stbl[index],
653 JFS_SBI(sb)->mntflag);
654 } else {
655
656
657 cmp = dtCompare(&ciKey, p, stbl[index]);
658
659
660 }
661 if (cmp == 0) {
662
663
664
665
666
667
668 if (p->header.flag & BT_LEAF) {
669 inumber = le32_to_cpu(
670 ((struct ldtentry *) & p->slot[stbl[index]])->inumber);
671
672
673
674
675 if (flag == JFS_LOOKUP) {
676 *data = inumber;
677 rc = 0;
678 goto out;
679 }
680
681
682
683
684 if (flag == JFS_CREATE) {
685 *data = inumber;
686 rc = -EEXIST;
687 goto out;
688 }
689
690
691
692
693 if ((flag == JFS_REMOVE ||
694 flag == JFS_RENAME) &&
695 *data != inumber) {
696 rc = -ESTALE;
697 goto out;
698 }
699
700
701
702
703
704 *data = inumber;
705 btsp = btstack->top;
706 btsp->bn = bn;
707 btsp->index = index;
708 btsp->mp = mp;
709
710 rc = 0;
711 goto dtSearch_Exit1;
712 }
713
714
715
716
717 goto getChild;
718 }
719
720 if (cmp > 0) {
721 base = index + 1;
722 --lim;
723 }
724 }
725
726
727
728
729
730
731
732
733
734
735
736
737
738 if (p->header.flag & BT_LEAF) {
739
740
741
742 if (flag == JFS_LOOKUP || flag == JFS_REMOVE ||
743 flag == JFS_RENAME) {
744 rc = -ENOENT;
745 goto out;
746 }
747
748
749
750
751
752
753 *data = 0;
754 btsp = btstack->top;
755 btsp->bn = bn;
756 btsp->index = base;
757 btsp->mp = mp;
758
759 rc = 0;
760 goto dtSearch_Exit1;
761 }
762
763
764
765
766
767
768
769 index = base ? base - 1 : base;
770
771
772
773
774 getChild:
775
776 if (BT_STACK_FULL(btstack)) {
777
778
779
780 jfs_error(sb, "stack overrun!\n");
781 BT_STACK_DUMP(btstack);
782 rc = -EIO;
783 goto out;
784 }
785 btstack->nsplit++;
786
787
788 BT_PUSH(btstack, bn, index);
789
790
791 pxd = (pxd_t *) & p->slot[stbl[index]];
792 bn = addressPXD(pxd);
793 psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize;
794
795
796 DT_PUTPAGE(mp);
797 }
798
799 out:
800 DT_PUTPAGE(mp);
801
802 dtSearch_Exit1:
803
804 kfree(ciKey.name);
805
806 dtSearch_Exit2:
807
808 return rc;
809}
810
811
812
813
814
815
816
817
818
819
820
821
822int dtInsert(tid_t tid, struct inode *ip,
823 struct component_name * name, ino_t * fsn, struct btstack * btstack)
824{
825 int rc = 0;
826 struct metapage *mp;
827 dtpage_t *p;
828 s64 bn;
829 int index;
830 struct dtsplit split;
831 ddata_t data;
832 struct dt_lock *dtlck;
833 int n;
834 struct tlock *tlck;
835 struct lv *lv;
836
837
838
839
840
841
842
843
844 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index);
845
846
847
848
849 if (DO_INDEX(ip)) {
850 if (JFS_IP(ip)->next_index == DIREND) {
851 DT_PUTPAGE(mp);
852 return -EMLINK;
853 }
854 n = NDTLEAF(name->namlen);
855 data.leaf.tid = tid;
856 data.leaf.ip = ip;
857 } else {
858 n = NDTLEAF_LEGACY(name->namlen);
859 data.leaf.ip = NULL;
860 }
861 data.leaf.ino = *fsn;
862
863
864
865
866
867
868
869
870 if (n > p->header.freecnt) {
871 split.mp = mp;
872 split.index = index;
873 split.nslot = n;
874 split.key = name;
875 split.data = &data;
876 rc = dtSplitUp(tid, ip, &split, btstack);
877 return rc;
878 }
879
880
881
882
883
884
885 BT_MARK_DIRTY(mp, ip);
886
887
888
889 tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY);
890 dtlck = (struct dt_lock *) & tlck->lock;
891 ASSERT(dtlck->index == 0);
892 lv = & dtlck->lv[0];
893
894
895 lv->offset = 0;
896 lv->length = 1;
897 dtlck->index++;
898
899 dtInsertEntry(p, index, name, &data, &dtlck);
900
901
902 if (!(p->header.flag & BT_ROOT)) {
903 if (dtlck->index >= dtlck->maxcnt)
904 dtlck = (struct dt_lock *) txLinelock(dtlck);
905 lv = & dtlck->lv[dtlck->index];
906 n = index >> L2DTSLOTSIZE;
907 lv->offset = p->header.stblindex + n;
908 lv->length =
909 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1;
910 dtlck->index++;
911 }
912
913
914 DT_PUTPAGE(mp);
915
916 return 0;
917}
918
919
920
921
922
923
924
925
926
927
928
929
930
931static int dtSplitUp(tid_t tid,
932 struct inode *ip, struct dtsplit * split, struct btstack * btstack)
933{
934 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
935 int rc = 0;
936 struct metapage *smp;
937 dtpage_t *sp;
938 struct metapage *rmp;
939 dtpage_t *rp;
940 pxd_t rpxd;
941 struct metapage *lmp;
942 dtpage_t *lp;
943 int skip;
944 struct btframe *parent;
945 s64 xaddr, nxaddr;
946 int xlen, xsize;
947 struct pxdlist pxdlist;
948 pxd_t *pxd;
949 struct component_name key = { 0, NULL };
950 ddata_t *data = split->data;
951 int n;
952 struct dt_lock *dtlck;
953 struct tlock *tlck;
954 struct lv *lv;
955 int quota_allocation = 0;
956
957
958 smp = split->mp;
959 sp = DT_PAGE(ip, smp);
960
961 key.name = kmalloc_array(JFS_NAME_MAX + 2, sizeof(wchar_t), GFP_NOFS);
962 if (!key.name) {
963 DT_PUTPAGE(smp);
964 rc = -ENOMEM;
965 goto dtSplitUp_Exit;
966 }
967
968
969
970
971
972
973
974
975
976
977 if (sp->header.flag & BT_ROOT) {
978
979
980
981 xlen = 1;
982 n = sbi->bsize >> L2DTSLOTSIZE;
983 n -= (n + 31) >> L2DTSLOTSIZE;
984 n -= DTROOTMAXSLOT - sp->header.freecnt;
985 if (n <= split->nslot)
986 xlen++;
987 if ((rc = dbAlloc(ip, 0, (s64) xlen, &xaddr))) {
988 DT_PUTPAGE(smp);
989 goto freeKeyName;
990 }
991
992 pxdlist.maxnpxd = 1;
993 pxdlist.npxd = 0;
994 pxd = &pxdlist.pxd[0];
995 PXDaddress(pxd, xaddr);
996 PXDlength(pxd, xlen);
997 split->pxdlist = &pxdlist;
998 rc = dtSplitRoot(tid, ip, split, &rmp);
999
1000 if (rc)
1001 dbFree(ip, xaddr, xlen);
1002 else
1003 DT_PUTPAGE(rmp);
1004
1005 DT_PUTPAGE(smp);
1006
1007 if (!DO_INDEX(ip))
1008 ip->i_size = xlen << sbi->l2bsize;
1009
1010 goto freeKeyName;
1011 }
1012
1013
1014
1015
1016
1017
1018
1019 pxd = &sp->header.self;
1020 xlen = lengthPXD(pxd);
1021 xsize = xlen << sbi->l2bsize;
1022 if (xsize < PSIZE) {
1023 xaddr = addressPXD(pxd);
1024 n = xsize >> L2DTSLOTSIZE;
1025 n -= (n + 31) >> L2DTSLOTSIZE;
1026 if ((n + sp->header.freecnt) <= split->nslot)
1027 n = xlen + (xlen << 1);
1028 else
1029 n = xlen;
1030
1031
1032 rc = dquot_alloc_block(ip, n);
1033 if (rc)
1034 goto extendOut;
1035 quota_allocation += n;
1036
1037 if ((rc = dbReAlloc(sbi->ipbmap, xaddr, (s64) xlen,
1038 (s64) n, &nxaddr)))
1039 goto extendOut;
1040
1041 pxdlist.maxnpxd = 1;
1042 pxdlist.npxd = 0;
1043 pxd = &pxdlist.pxd[0];
1044 PXDaddress(pxd, nxaddr);
1045 PXDlength(pxd, xlen + n);
1046 split->pxdlist = &pxdlist;
1047 if ((rc = dtExtendPage(tid, ip, split, btstack))) {
1048 nxaddr = addressPXD(pxd);
1049 if (xaddr != nxaddr) {
1050
1051 xlen = lengthPXD(pxd);
1052 dbFree(ip, nxaddr, (s64) xlen);
1053 } else {
1054
1055 xlen = lengthPXD(pxd) - n;
1056 xaddr = addressPXD(pxd) + xlen;
1057 dbFree(ip, xaddr, (s64) n);
1058 }
1059 } else if (!DO_INDEX(ip))
1060 ip->i_size = lengthPXD(pxd) << sbi->l2bsize;
1061
1062
1063 extendOut:
1064 DT_PUTPAGE(smp);
1065 goto freeKeyName;
1066 }
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079 n = btstack->nsplit;
1080 pxdlist.maxnpxd = pxdlist.npxd = 0;
1081 xlen = sbi->nbperpage;
1082 for (pxd = pxdlist.pxd; n > 0; n--, pxd++) {
1083 if ((rc = dbAlloc(ip, 0, (s64) xlen, &xaddr)) == 0) {
1084 PXDaddress(pxd, xaddr);
1085 PXDlength(pxd, xlen);
1086 pxdlist.maxnpxd++;
1087 continue;
1088 }
1089
1090 DT_PUTPAGE(smp);
1091
1092
1093 goto splitOut;
1094 }
1095
1096 split->pxdlist = &pxdlist;
1097 if ((rc = dtSplitPage(tid, ip, split, &rmp, &rp, &rpxd))) {
1098 DT_PUTPAGE(smp);
1099
1100
1101 goto splitOut;
1102 }
1103
1104 if (!DO_INDEX(ip))
1105 ip->i_size += PSIZE;
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128 while ((parent = BT_POP(btstack)) != NULL) {
1129
1130
1131
1132 lmp = smp;
1133 lp = sp;
1134
1135
1136
1137
1138
1139 DT_GETPAGE(ip, parent->bn, smp, PSIZE, sp, rc);
1140 if (rc) {
1141 DT_PUTPAGE(lmp);
1142 DT_PUTPAGE(rmp);
1143 goto splitOut;
1144 }
1145
1146
1147
1148
1149
1150 skip = parent->index + 1;
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177 switch (rp->header.flag & BT_TYPE) {
1178 case BT_LEAF:
1179
1180
1181
1182
1183
1184 if ((sp->header.flag & BT_ROOT && skip > 1) ||
1185 sp->header.prev != 0 || skip > 1) {
1186
1187 rc = ciGetLeafPrefixKey(lp,
1188 lp->header.nextindex-1,
1189 rp, 0, &key,
1190 sbi->mntflag);
1191 if (rc) {
1192 DT_PUTPAGE(lmp);
1193 DT_PUTPAGE(rmp);
1194 DT_PUTPAGE(smp);
1195 goto splitOut;
1196 }
1197 } else {
1198
1199
1200
1201
1202 dtGetKey(rp, 0, &key, sbi->mntflag);
1203 key.name[key.namlen] = 0;
1204
1205 if ((sbi->mntflag & JFS_OS2) == JFS_OS2)
1206 ciToUpper(&key);
1207 }
1208
1209 n = NDTINTERNAL(key.namlen);
1210 break;
1211
1212 case BT_INTERNAL:
1213 dtGetKey(rp, 0, &key, sbi->mntflag);
1214 n = NDTINTERNAL(key.namlen);
1215 break;
1216
1217 default:
1218 jfs_err("dtSplitUp(): UFO!");
1219 break;
1220 }
1221
1222
1223 DT_PUTPAGE(lmp);
1224
1225
1226
1227
1228 data->xd = rpxd;
1229
1230
1231
1232
1233 if (n > sp->header.freecnt) {
1234
1235 split->mp = smp;
1236 split->index = skip;
1237 split->nslot = n;
1238 split->key = &key;
1239
1240
1241
1242 DT_PUTPAGE(rmp);
1243
1244
1245
1246
1247
1248 rc = (sp->header.flag & BT_ROOT) ?
1249 dtSplitRoot(tid, ip, split, &rmp) :
1250 dtSplitPage(tid, ip, split, &rmp, &rp, &rpxd);
1251 if (rc) {
1252 DT_PUTPAGE(smp);
1253 goto splitOut;
1254 }
1255
1256
1257 }
1258
1259
1260
1261 else {
1262 BT_MARK_DIRTY(smp, ip);
1263
1264
1265
1266 tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY);
1267 dtlck = (struct dt_lock *) & tlck->lock;
1268 ASSERT(dtlck->index == 0);
1269 lv = & dtlck->lv[0];
1270
1271
1272 lv->offset = 0;
1273 lv->length = 1;
1274 dtlck->index++;
1275
1276
1277 if (!(sp->header.flag & BT_ROOT)) {
1278 lv++;
1279 n = skip >> L2DTSLOTSIZE;
1280 lv->offset = sp->header.stblindex + n;
1281 lv->length =
1282 ((sp->header.nextindex -
1283 1) >> L2DTSLOTSIZE) - n + 1;
1284 dtlck->index++;
1285 }
1286
1287 dtInsertEntry(sp, skip, &key, data, &dtlck);
1288
1289
1290 break;
1291 }
1292 }
1293
1294
1295 DT_PUTPAGE(smp);
1296 DT_PUTPAGE(rmp);
1297
1298
1299
1300
1301 splitOut:
1302 n = pxdlist.npxd;
1303 pxd = &pxdlist.pxd[n];
1304 for (; n < pxdlist.maxnpxd; n++, pxd++)
1305 dbFree(ip, addressPXD(pxd), (s64) lengthPXD(pxd));
1306
1307 freeKeyName:
1308 kfree(key.name);
1309
1310
1311 if (rc && quota_allocation)
1312 dquot_free_block(ip, quota_allocation);
1313
1314 dtSplitUp_Exit:
1315
1316 return rc;
1317}
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331static int dtSplitPage(tid_t tid, struct inode *ip, struct dtsplit * split,
1332 struct metapage ** rmpp, dtpage_t ** rpp, pxd_t * rpxdp)
1333{
1334 int rc = 0;
1335 struct metapage *smp;
1336 dtpage_t *sp;
1337 struct metapage *rmp;
1338 dtpage_t *rp;
1339 s64 rbn;
1340 struct metapage *mp;
1341 dtpage_t *p;
1342 s64 nextbn;
1343 struct pxdlist *pxdlist;
1344 pxd_t *pxd;
1345 int skip, nextindex, half, left, nxt, off, si;
1346 struct ldtentry *ldtentry;
1347 struct idtentry *idtentry;
1348 u8 *stbl;
1349 struct dtslot *f;
1350 int fsi, stblsize;
1351 int n;
1352 struct dt_lock *sdtlck, *rdtlck;
1353 struct tlock *tlck;
1354 struct dt_lock *dtlck;
1355 struct lv *slv, *rlv, *lv;
1356
1357
1358 smp = split->mp;
1359 sp = DT_PAGE(ip, smp);
1360
1361
1362
1363
1364 pxdlist = split->pxdlist;
1365 pxd = &pxdlist->pxd[pxdlist->npxd];
1366 pxdlist->npxd++;
1367 rbn = addressPXD(pxd);
1368 rmp = get_metapage(ip, rbn, PSIZE, 1);
1369 if (rmp == NULL)
1370 return -EIO;
1371
1372
1373 rc = dquot_alloc_block(ip, lengthPXD(pxd));
1374 if (rc) {
1375 release_metapage(rmp);
1376 return rc;
1377 }
1378
1379 jfs_info("dtSplitPage: ip:0x%p smp:0x%p rmp:0x%p", ip, smp, rmp);
1380
1381 BT_MARK_DIRTY(rmp, ip);
1382
1383
1384
1385 tlck = txLock(tid, ip, rmp, tlckDTREE | tlckNEW);
1386 rdtlck = (struct dt_lock *) & tlck->lock;
1387
1388 rp = (dtpage_t *) rmp->data;
1389 *rpp = rp;
1390 rp->header.self = *pxd;
1391
1392 BT_MARK_DIRTY(smp, ip);
1393
1394
1395
1396
1397
1398 tlck = txLock(tid, ip, smp, tlckDTREE | tlckENTRY);
1399 sdtlck = (struct dt_lock *) & tlck->lock;
1400
1401
1402 ASSERT(sdtlck->index == 0);
1403 slv = & sdtlck->lv[0];
1404 slv->offset = 0;
1405 slv->length = 1;
1406 sdtlck->index++;
1407
1408
1409
1410
1411 nextbn = le64_to_cpu(sp->header.next);
1412 rp->header.next = cpu_to_le64(nextbn);
1413 rp->header.prev = cpu_to_le64(addressPXD(&sp->header.self));
1414 sp->header.next = cpu_to_le64(rbn);
1415
1416
1417
1418
1419 rp->header.flag = sp->header.flag;
1420
1421
1422 rp->header.nextindex = 0;
1423 rp->header.stblindex = 1;
1424
1425 n = PSIZE >> L2DTSLOTSIZE;
1426 rp->header.maxslot = n;
1427 stblsize = (n + 31) >> L2DTSLOTSIZE;
1428
1429
1430 fsi = rp->header.stblindex + stblsize;
1431 rp->header.freelist = fsi;
1432 rp->header.freecnt = rp->header.maxslot - fsi;
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447 if (nextbn == 0 && split->index == sp->header.nextindex) {
1448
1449 rlv = & rdtlck->lv[rdtlck->index];
1450 rlv->offset = 0;
1451 rlv->length = 2;
1452 rdtlck->index++;
1453
1454
1455
1456
1457 f = &rp->slot[fsi];
1458 for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
1459 f->next = fsi;
1460 f->next = -1;
1461
1462
1463 dtInsertEntry(rp, 0, split->key, split->data, &rdtlck);
1464
1465 goto out;
1466 }
1467
1468
1469
1470
1471
1472
1473
1474
1475 if (nextbn != 0) {
1476 DT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
1477 if (rc) {
1478 discard_metapage(rmp);
1479 return rc;
1480 }
1481
1482 BT_MARK_DIRTY(mp, ip);
1483
1484
1485
1486 tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK);
1487 jfs_info("dtSplitPage: tlck = 0x%p, ip = 0x%p, mp=0x%p",
1488 tlck, ip, mp);
1489 dtlck = (struct dt_lock *) & tlck->lock;
1490
1491
1492 lv = & dtlck->lv[dtlck->index];
1493 lv->offset = 0;
1494 lv->length = 1;
1495 dtlck->index++;
1496
1497 p->header.prev = cpu_to_le64(rbn);
1498
1499 DT_PUTPAGE(mp);
1500 }
1501
1502
1503
1504
1505 skip = split->index;
1506 half = (PSIZE >> L2DTSLOTSIZE) >> 1;
1507 left = 0;
1508
1509
1510
1511
1512
1513
1514
1515 stbl = (u8 *) & sp->slot[sp->header.stblindex];
1516 nextindex = sp->header.nextindex;
1517 for (nxt = off = 0; nxt < nextindex; ++off) {
1518 if (off == skip)
1519
1520 n = split->nslot;
1521 else {
1522 si = stbl[nxt];
1523 switch (sp->header.flag & BT_TYPE) {
1524 case BT_LEAF:
1525 ldtentry = (struct ldtentry *) & sp->slot[si];
1526 if (DO_INDEX(ip))
1527 n = NDTLEAF(ldtentry->namlen);
1528 else
1529 n = NDTLEAF_LEGACY(ldtentry->
1530 namlen);
1531 break;
1532
1533 case BT_INTERNAL:
1534 idtentry = (struct idtentry *) & sp->slot[si];
1535 n = NDTINTERNAL(idtentry->namlen);
1536 break;
1537
1538 default:
1539 break;
1540 }
1541
1542 ++nxt;
1543 }
1544
1545 left += n;
1546 if (left >= half)
1547 break;
1548 }
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561 rlv = & rdtlck->lv[rdtlck->index];
1562 rlv->offset = 0;
1563 rlv->length = 5;
1564 rdtlck->index++;
1565
1566 dtMoveEntry(sp, nxt, rp, &sdtlck, &rdtlck, DO_INDEX(ip));
1567
1568 sp->header.nextindex = nxt;
1569
1570
1571
1572
1573 fsi = rp->header.freelist;
1574 f = &rp->slot[fsi];
1575 for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
1576 f->next = fsi;
1577 f->next = -1;
1578
1579
1580
1581
1582 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) {
1583 s64 lblock;
1584
1585 mp = NULL;
1586 stbl = DT_GETSTBL(rp);
1587 for (n = 0; n < rp->header.nextindex; n++) {
1588 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]];
1589 modify_index(tid, ip, le32_to_cpu(ldtentry->index),
1590 rbn, n, &mp, &lblock);
1591 }
1592 if (mp)
1593 release_metapage(mp);
1594 }
1595
1596
1597
1598
1599 if (skip <= off) {
1600
1601 dtInsertEntry(sp, skip, split->key, split->data, &sdtlck);
1602
1603
1604 if (sdtlck->index >= sdtlck->maxcnt)
1605 sdtlck = (struct dt_lock *) txLinelock(sdtlck);
1606 slv = & sdtlck->lv[sdtlck->index];
1607 n = skip >> L2DTSLOTSIZE;
1608 slv->offset = sp->header.stblindex + n;
1609 slv->length =
1610 ((sp->header.nextindex - 1) >> L2DTSLOTSIZE) - n + 1;
1611 sdtlck->index++;
1612 }
1613
1614
1615
1616 else {
1617
1618 skip -= nxt;
1619
1620
1621 dtInsertEntry(rp, skip, split->key, split->data, &rdtlck);
1622 }
1623
1624 out:
1625 *rmpp = rmp;
1626 *rpxdp = *pxd;
1627
1628 return rc;
1629}
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643static int dtExtendPage(tid_t tid,
1644 struct inode *ip, struct dtsplit * split, struct btstack * btstack)
1645{
1646 struct super_block *sb = ip->i_sb;
1647 int rc;
1648 struct metapage *smp, *pmp, *mp;
1649 dtpage_t *sp, *pp;
1650 struct pxdlist *pxdlist;
1651 pxd_t *pxd, *tpxd;
1652 int xlen, xsize;
1653 int newstblindex, newstblsize;
1654 int oldstblindex, oldstblsize;
1655 int fsi, last;
1656 struct dtslot *f;
1657 struct btframe *parent;
1658 int n;
1659 struct dt_lock *dtlck;
1660 s64 xaddr, txaddr;
1661 struct tlock *tlck;
1662 struct pxd_lock *pxdlock;
1663 struct lv *lv;
1664 uint type;
1665 struct ldtentry *ldtentry;
1666 u8 *stbl;
1667
1668
1669 smp = split->mp;
1670 sp = DT_PAGE(ip, smp);
1671
1672
1673 parent = BT_POP(btstack);
1674 DT_GETPAGE(ip, parent->bn, pmp, PSIZE, pp, rc);
1675 if (rc)
1676 return (rc);
1677
1678
1679
1680
1681 pxdlist = split->pxdlist;
1682 pxd = &pxdlist->pxd[pxdlist->npxd];
1683 pxdlist->npxd++;
1684
1685 xaddr = addressPXD(pxd);
1686 tpxd = &sp->header.self;
1687 txaddr = addressPXD(tpxd);
1688
1689 if (xaddr == txaddr) {
1690 type = tlckEXTEND;
1691 }
1692
1693 else {
1694 type = tlckNEW;
1695
1696
1697 tlck = txMaplock(tid, ip, tlckDTREE | tlckRELOCATE);
1698 pxdlock = (struct pxd_lock *) & tlck->lock;
1699 pxdlock->flag = mlckFREEPXD;
1700 pxdlock->pxd = sp->header.self;
1701 pxdlock->index = 1;
1702
1703
1704
1705
1706 if (DO_INDEX(ip)) {
1707 s64 lblock;
1708
1709 mp = NULL;
1710 stbl = DT_GETSTBL(sp);
1711 for (n = 0; n < sp->header.nextindex; n++) {
1712 ldtentry =
1713 (struct ldtentry *) & sp->slot[stbl[n]];
1714 modify_index(tid, ip,
1715 le32_to_cpu(ldtentry->index),
1716 xaddr, n, &mp, &lblock);
1717 }
1718 if (mp)
1719 release_metapage(mp);
1720 }
1721 }
1722
1723
1724
1725
1726 sp->header.self = *pxd;
1727
1728 jfs_info("dtExtendPage: ip:0x%p smp:0x%p sp:0x%p", ip, smp, sp);
1729
1730 BT_MARK_DIRTY(smp, ip);
1731
1732
1733
1734 tlck = txLock(tid, ip, smp, tlckDTREE | type);
1735 dtlck = (struct dt_lock *) & tlck->lock;
1736 lv = & dtlck->lv[0];
1737
1738
1739 xlen = lengthPXD(pxd);
1740 xsize = xlen << JFS_SBI(sb)->l2bsize;
1741
1742
1743
1744
1745 oldstblindex = sp->header.stblindex;
1746 oldstblsize = (sp->header.maxslot + 31) >> L2DTSLOTSIZE;
1747 newstblindex = sp->header.maxslot;
1748 n = xsize >> L2DTSLOTSIZE;
1749 newstblsize = (n + 31) >> L2DTSLOTSIZE;
1750 memcpy(&sp->slot[newstblindex], &sp->slot[oldstblindex],
1751 sp->header.nextindex);
1752
1753
1754
1755
1756 if (type == tlckEXTEND) {
1757
1758 lv->offset = 0;
1759 lv->length = 1;
1760 dtlck->index++;
1761 lv++;
1762
1763
1764 lv->offset = newstblindex;
1765 lv->length = newstblsize;
1766 }
1767
1768
1769
1770 else {
1771 lv->offset = 0;
1772 lv->length = sp->header.maxslot + newstblsize;
1773 }
1774
1775 dtlck->index++;
1776
1777 sp->header.maxslot = n;
1778 sp->header.stblindex = newstblindex;
1779
1780
1781
1782
1783
1784 fsi = oldstblindex;
1785 f = &sp->slot[fsi];
1786 last = sp->header.freelist;
1787 for (n = 0; n < oldstblsize; n++, fsi++, f++) {
1788 f->next = last;
1789 last = fsi;
1790 }
1791 sp->header.freelist = last;
1792 sp->header.freecnt += oldstblsize;
1793
1794
1795
1796
1797
1798 fsi = n = newstblindex + newstblsize;
1799 f = &sp->slot[fsi];
1800 for (fsi++; fsi < sp->header.maxslot; f++, fsi++)
1801 f->next = fsi;
1802 f->next = -1;
1803
1804
1805 fsi = sp->header.freelist;
1806 if (fsi == -1)
1807 sp->header.freelist = n;
1808 else {
1809 do {
1810 f = &sp->slot[fsi];
1811 fsi = f->next;
1812 } while (fsi != -1);
1813
1814 f->next = n;
1815 }
1816
1817 sp->header.freecnt += sp->header.maxslot - n;
1818
1819
1820
1821
1822 dtInsertEntry(sp, split->index, split->key, split->data, &dtlck);
1823
1824 BT_MARK_DIRTY(pmp, ip);
1825
1826
1827
1828 if (type == tlckEXTEND) {
1829 n = sp->header.maxslot >> 2;
1830 if (sp->header.freelist < n)
1831 dtLinelockFreelist(sp, n, &dtlck);
1832 }
1833
1834
1835
1836
1837
1838
1839
1840 tlck = txLock(tid, ip, pmp, tlckDTREE | tlckENTRY);
1841 dtlck = (struct dt_lock *) & tlck->lock;
1842 lv = & dtlck->lv[dtlck->index];
1843
1844
1845 lv->offset = 1;
1846 lv->length = 1;
1847 dtlck->index++;
1848
1849
1850 tpxd = (pxd_t *) & pp->slot[1];
1851 *tpxd = *pxd;
1852
1853 DT_PUTPAGE(pmp);
1854 return 0;
1855}
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876static int dtSplitRoot(tid_t tid,
1877 struct inode *ip, struct dtsplit * split, struct metapage ** rmpp)
1878{
1879 struct super_block *sb = ip->i_sb;
1880 struct metapage *smp;
1881 dtroot_t *sp;
1882 struct metapage *rmp;
1883 dtpage_t *rp;
1884 s64 rbn;
1885 int xlen;
1886 int xsize;
1887 struct dtslot *f;
1888 s8 *stbl;
1889 int fsi, stblsize, n;
1890 struct idtentry *s;
1891 pxd_t *ppxd;
1892 struct pxdlist *pxdlist;
1893 pxd_t *pxd;
1894 struct dt_lock *dtlck;
1895 struct tlock *tlck;
1896 struct lv *lv;
1897 int rc;
1898
1899
1900 smp = split->mp;
1901 sp = &JFS_IP(ip)->i_dtroot;
1902
1903
1904
1905
1906
1907
1908
1909 pxdlist = split->pxdlist;
1910 pxd = &pxdlist->pxd[pxdlist->npxd];
1911 pxdlist->npxd++;
1912 rbn = addressPXD(pxd);
1913 xlen = lengthPXD(pxd);
1914 xsize = xlen << JFS_SBI(sb)->l2bsize;
1915 rmp = get_metapage(ip, rbn, xsize, 1);
1916 if (!rmp)
1917 return -EIO;
1918
1919 rp = rmp->data;
1920
1921
1922 rc = dquot_alloc_block(ip, lengthPXD(pxd));
1923 if (rc) {
1924 release_metapage(rmp);
1925 return rc;
1926 }
1927
1928 BT_MARK_DIRTY(rmp, ip);
1929
1930
1931
1932 tlck = txLock(tid, ip, rmp, tlckDTREE | tlckNEW);
1933 dtlck = (struct dt_lock *) & tlck->lock;
1934
1935 rp->header.flag =
1936 (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
1937 rp->header.self = *pxd;
1938
1939
1940 rp->header.next = 0;
1941 rp->header.prev = 0;
1942
1943
1944
1945
1946
1947 ASSERT(dtlck->index == 0);
1948 lv = & dtlck->lv[0];
1949 lv->offset = 0;
1950 lv->length = 10;
1951 dtlck->index++;
1952
1953 n = xsize >> L2DTSLOTSIZE;
1954 rp->header.maxslot = n;
1955 stblsize = (n + 31) >> L2DTSLOTSIZE;
1956
1957
1958 rp->header.stblindex = DTROOTMAXSLOT;
1959 stbl = (s8 *) & rp->slot[DTROOTMAXSLOT];
1960 memcpy(stbl, sp->header.stbl, sp->header.nextindex);
1961 rp->header.nextindex = sp->header.nextindex;
1962
1963
1964 memcpy(&rp->slot[1], &sp->slot[1], IDATASIZE);
1965
1966
1967
1968
1969
1970 fsi = n = DTROOTMAXSLOT + stblsize;
1971 f = &rp->slot[fsi];
1972 for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
1973 f->next = fsi;
1974 f->next = -1;
1975
1976
1977 fsi = sp->header.freelist;
1978 if (fsi == -1)
1979 rp->header.freelist = n;
1980 else {
1981 rp->header.freelist = fsi;
1982
1983 do {
1984 f = &rp->slot[fsi];
1985 fsi = f->next;
1986 } while (fsi != -1);
1987
1988 f->next = n;
1989 }
1990
1991 rp->header.freecnt = sp->header.freecnt + rp->header.maxslot - n;
1992
1993
1994
1995
1996 if ((rp->header.flag & BT_LEAF) && DO_INDEX(ip)) {
1997 s64 lblock;
1998 struct metapage *mp = NULL;
1999 struct ldtentry *ldtentry;
2000
2001 stbl = DT_GETSTBL(rp);
2002 for (n = 0; n < rp->header.nextindex; n++) {
2003 ldtentry = (struct ldtentry *) & rp->slot[stbl[n]];
2004 modify_index(tid, ip, le32_to_cpu(ldtentry->index),
2005 rbn, n, &mp, &lblock);
2006 }
2007 if (mp)
2008 release_metapage(mp);
2009 }
2010
2011
2012
2013
2014 dtInsertEntry(rp, split->index, split->key, split->data, &dtlck);
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025 BT_MARK_DIRTY(smp, ip);
2026
2027
2028
2029 tlck = txLock(tid, ip, smp, tlckDTREE | tlckNEW | tlckBTROOT);
2030 dtlck = (struct dt_lock *) & tlck->lock;
2031
2032
2033 ASSERT(dtlck->index == 0);
2034 lv = & dtlck->lv[0];
2035 lv->offset = 0;
2036 lv->length = DTROOTMAXSLOT;
2037 dtlck->index++;
2038
2039
2040 if (sp->header.flag & BT_LEAF) {
2041 sp->header.flag &= ~BT_LEAF;
2042 sp->header.flag |= BT_INTERNAL;
2043 }
2044
2045
2046 s = (struct idtentry *) & sp->slot[DTENTRYSTART];
2047 ppxd = (pxd_t *) s;
2048 *ppxd = *pxd;
2049 s->next = -1;
2050 s->namlen = 0;
2051
2052 stbl = sp->header.stbl;
2053 stbl[0] = DTENTRYSTART;
2054 sp->header.nextindex = 1;
2055
2056
2057 fsi = DTENTRYSTART + 1;
2058 f = &sp->slot[fsi];
2059
2060
2061 for (fsi++; fsi < DTROOTMAXSLOT; f++, fsi++)
2062 f->next = fsi;
2063 f->next = -1;
2064
2065 sp->header.freelist = DTENTRYSTART + 1;
2066 sp->header.freecnt = DTROOTMAXSLOT - (DTENTRYSTART + 1);
2067
2068 *rmpp = rmp;
2069
2070 return 0;
2071}
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083int dtDelete(tid_t tid,
2084 struct inode *ip, struct component_name * key, ino_t * ino, int flag)
2085{
2086 int rc = 0;
2087 s64 bn;
2088 struct metapage *mp, *imp;
2089 dtpage_t *p;
2090 int index;
2091 struct btstack btstack;
2092 struct dt_lock *dtlck;
2093 struct tlock *tlck;
2094 struct lv *lv;
2095 int i;
2096 struct ldtentry *ldtentry;
2097 u8 *stbl;
2098 u32 table_index, next_index;
2099 struct metapage *nmp;
2100 dtpage_t *np;
2101
2102
2103
2104
2105
2106
2107 if ((rc = dtSearch(ip, key, ino, &btstack, flag)))
2108 return rc;
2109
2110
2111 DT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
2112
2113
2114
2115
2116
2117
2118 if (DO_INDEX(ip)) {
2119 stbl = DT_GETSTBL(p);
2120 ldtentry = (struct ldtentry *) & p->slot[stbl[index]];
2121 table_index = le32_to_cpu(ldtentry->index);
2122 if (index == (p->header.nextindex - 1)) {
2123
2124
2125
2126 if ((p->header.flag & BT_ROOT)
2127 || (p->header.next == 0))
2128 next_index = -1;
2129 else {
2130
2131 DT_GETPAGE(ip, le64_to_cpu(p->header.next),
2132 nmp, PSIZE, np, rc);
2133 if (rc)
2134 next_index = -1;
2135 else {
2136 stbl = DT_GETSTBL(np);
2137 ldtentry =
2138 (struct ldtentry *) & np->
2139 slot[stbl[0]];
2140 next_index =
2141 le32_to_cpu(ldtentry->index);
2142 DT_PUTPAGE(nmp);
2143 }
2144 }
2145 } else {
2146 ldtentry =
2147 (struct ldtentry *) & p->slot[stbl[index + 1]];
2148 next_index = le32_to_cpu(ldtentry->index);
2149 }
2150 free_index(tid, ip, table_index, next_index);
2151 }
2152
2153
2154
2155 if (p->header.nextindex == 1) {
2156
2157 rc = dtDeleteUp(tid, ip, mp, p, &btstack);
2158 }
2159
2160
2161
2162
2163
2164 else {
2165 BT_MARK_DIRTY(mp, ip);
2166
2167
2168
2169 tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY);
2170 dtlck = (struct dt_lock *) & tlck->lock;
2171
2172
2173
2174
2175
2176
2177
2178
2179 if (dtlck->index >= dtlck->maxcnt)
2180 dtlck = (struct dt_lock *) txLinelock(dtlck);
2181 lv = & dtlck->lv[dtlck->index];
2182 lv->offset = 0;
2183 lv->length = 1;
2184 dtlck->index++;
2185
2186
2187 if (!(p->header.flag & BT_ROOT)) {
2188 if (dtlck->index >= dtlck->maxcnt)
2189 dtlck = (struct dt_lock *) txLinelock(dtlck);
2190 lv = & dtlck->lv[dtlck->index];
2191 i = index >> L2DTSLOTSIZE;
2192 lv->offset = p->header.stblindex + i;
2193 lv->length =
2194 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) -
2195 i + 1;
2196 dtlck->index++;
2197 }
2198
2199
2200 dtDeleteEntry(p, index, &dtlck);
2201
2202
2203
2204
2205 if (DO_INDEX(ip) && index < p->header.nextindex) {
2206 s64 lblock;
2207
2208 imp = NULL;
2209 stbl = DT_GETSTBL(p);
2210 for (i = index; i < p->header.nextindex; i++) {
2211 ldtentry =
2212 (struct ldtentry *) & p->slot[stbl[i]];
2213 modify_index(tid, ip,
2214 le32_to_cpu(ldtentry->index),
2215 bn, i, &imp, &lblock);
2216 }
2217 if (imp)
2218 release_metapage(imp);
2219 }
2220
2221 DT_PUTPAGE(mp);
2222 }
2223
2224 return rc;
2225}
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238static int dtDeleteUp(tid_t tid, struct inode *ip,
2239 struct metapage * fmp, dtpage_t * fp, struct btstack * btstack)
2240{
2241 int rc = 0;
2242 struct metapage *mp;
2243 dtpage_t *p;
2244 int index, nextindex;
2245 int xlen;
2246 struct btframe *parent;
2247 struct dt_lock *dtlck;
2248 struct tlock *tlck;
2249 struct lv *lv;
2250 struct pxd_lock *pxdlock;
2251 int i;
2252
2253
2254
2255
2256 if (BT_IS_ROOT(fmp)) {
2257
2258
2259
2260
2261
2262 dtInitRoot(tid, ip, PARENT(ip));
2263
2264 DT_PUTPAGE(fmp);
2265
2266 return 0;
2267 }
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279 tlck = txMaplock(tid, ip, tlckDTREE | tlckFREE);
2280 pxdlock = (struct pxd_lock *) & tlck->lock;
2281 pxdlock->flag = mlckFREEPXD;
2282 pxdlock->pxd = fp->header.self;
2283 pxdlock->index = 1;
2284
2285
2286 if ((rc = dtRelink(tid, ip, fp))) {
2287 BT_PUTPAGE(fmp);
2288 return rc;
2289 }
2290
2291 xlen = lengthPXD(&fp->header.self);
2292
2293
2294 dquot_free_block(ip, xlen);
2295
2296
2297 discard_metapage(fmp);
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307 while ((parent = BT_POP(btstack)) != NULL) {
2308
2309 DT_GETPAGE(ip, parent->bn, mp, PSIZE, p, rc);
2310 if (rc)
2311 return rc;
2312
2313
2314
2315
2316 index = parent->index;
2317
2318
2319
2320
2321 nextindex = p->header.nextindex;
2322
2323
2324
2325
2326
2327
2328 if (nextindex == 1) {
2329
2330
2331
2332 if (p->header.flag & BT_ROOT) {
2333
2334
2335
2336
2337
2338 dtInitRoot(tid, ip, PARENT(ip));
2339
2340 DT_PUTPAGE(mp);
2341
2342 return 0;
2343 }
2344
2345
2346
2347 else {
2348
2349
2350
2351
2352
2353 tlck =
2354 txMaplock(tid, ip,
2355 tlckDTREE | tlckFREE);
2356 pxdlock = (struct pxd_lock *) & tlck->lock;
2357 pxdlock->flag = mlckFREEPXD;
2358 pxdlock->pxd = p->header.self;
2359 pxdlock->index = 1;
2360
2361
2362 if ((rc = dtRelink(tid, ip, p))) {
2363 DT_PUTPAGE(mp);
2364 return rc;
2365 }
2366
2367 xlen = lengthPXD(&p->header.self);
2368
2369
2370 dquot_free_block(ip, xlen);
2371
2372
2373 discard_metapage(mp);
2374
2375
2376 continue;
2377 }
2378 }
2379
2380
2381
2382
2383
2384
2385 BT_MARK_DIRTY(mp, ip);
2386
2387
2388
2389
2390
2391 tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY);
2392 dtlck = (struct dt_lock *) & tlck->lock;
2393
2394
2395 if (dtlck->index >= dtlck->maxcnt)
2396 dtlck = (struct dt_lock *) txLinelock(dtlck);
2397 lv = & dtlck->lv[dtlck->index];
2398 lv->offset = 0;
2399 lv->length = 1;
2400 dtlck->index++;
2401
2402
2403 if (!(p->header.flag & BT_ROOT)) {
2404 if (dtlck->index < dtlck->maxcnt)
2405 lv++;
2406 else {
2407 dtlck = (struct dt_lock *) txLinelock(dtlck);
2408 lv = & dtlck->lv[0];
2409 }
2410 i = index >> L2DTSLOTSIZE;
2411 lv->offset = p->header.stblindex + i;
2412 lv->length =
2413 ((p->header.nextindex - 1) >> L2DTSLOTSIZE) -
2414 i + 1;
2415 dtlck->index++;
2416 }
2417
2418
2419 dtDeleteEntry(p, index, &dtlck);
2420
2421
2422 if (index == 0 &&
2423 ((p->header.flag & BT_ROOT) || p->header.prev == 0))
2424 dtTruncateEntry(p, 0, &dtlck);
2425
2426
2427 DT_PUTPAGE(mp);
2428
2429
2430 break;
2431 }
2432
2433 if (!DO_INDEX(ip))
2434 ip->i_size -= PSIZE;
2435
2436 return 0;
2437}
2438
2439#ifdef _NOTYET
2440
2441
2442
2443
2444
2445
2446int dtRelocate(tid_t tid, struct inode *ip, s64 lmxaddr, pxd_t * opxd,
2447 s64 nxaddr)
2448{
2449 int rc = 0;
2450 struct metapage *mp, *pmp, *lmp, *rmp;
2451 dtpage_t *p, *pp, *rp = 0, *lp= 0;
2452 s64 bn;
2453 int index;
2454 struct btstack btstack;
2455 pxd_t *pxd;
2456 s64 oxaddr, nextbn, prevbn;
2457 int xlen, xsize;
2458 struct tlock *tlck;
2459 struct dt_lock *dtlck;
2460 struct pxd_lock *pxdlock;
2461 s8 *stbl;
2462 struct lv *lv;
2463
2464 oxaddr = addressPXD(opxd);
2465 xlen = lengthPXD(opxd);
2466
2467 jfs_info("dtRelocate: lmxaddr:%Ld xaddr:%Ld:%Ld xlen:%d",
2468 (long long)lmxaddr, (long long)oxaddr, (long long)nxaddr,
2469 xlen);
2470
2471
2472
2473
2474
2475 rc = dtSearchNode(ip, lmxaddr, opxd, &btstack);
2476 if (rc)
2477 return rc;
2478
2479
2480 DT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
2481 jfs_info("dtRelocate: parent router entry validated.");
2482
2483
2484
2485
2486
2487 DT_GETPAGE(ip, oxaddr, mp, PSIZE, p, rc);
2488 if (rc) {
2489
2490 DT_PUTPAGE(pmp);
2491 return rc;
2492 }
2493
2494
2495
2496
2497 rmp = NULL;
2498 if (p->header.next) {
2499 nextbn = le64_to_cpu(p->header.next);
2500 DT_GETPAGE(ip, nextbn, rmp, PSIZE, rp, rc);
2501 if (rc) {
2502 DT_PUTPAGE(mp);
2503 DT_PUTPAGE(pmp);
2504 return (rc);
2505 }
2506 }
2507
2508 lmp = NULL;
2509 if (p->header.prev) {
2510 prevbn = le64_to_cpu(p->header.prev);
2511 DT_GETPAGE(ip, prevbn, lmp, PSIZE, lp, rc);
2512 if (rc) {
2513 DT_PUTPAGE(mp);
2514 DT_PUTPAGE(pmp);
2515 if (rmp)
2516 DT_PUTPAGE(rmp);
2517 return (rc);
2518 }
2519 }
2520
2521
2522
2523
2524
2525
2526 if (lmp) {
2527 tlck = txLock(tid, ip, lmp, tlckDTREE | tlckRELINK);
2528 dtlck = (struct dt_lock *) & tlck->lock;
2529
2530 ASSERT(dtlck->index == 0);
2531 lv = & dtlck->lv[0];
2532 lv->offset = 0;
2533 lv->length = 1;
2534 dtlck->index++;
2535
2536 lp->header.next = cpu_to_le64(nxaddr);
2537 DT_PUTPAGE(lmp);
2538 }
2539
2540 if (rmp) {
2541 tlck = txLock(tid, ip, rmp, tlckDTREE | tlckRELINK);
2542 dtlck = (struct dt_lock *) & tlck->lock;
2543
2544 ASSERT(dtlck->index == 0);
2545 lv = & dtlck->lv[0];
2546 lv->offset = 0;
2547 lv->length = 1;
2548 dtlck->index++;
2549
2550 rp->header.prev = cpu_to_le64(nxaddr);
2551 DT_PUTPAGE(rmp);
2552 }
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563 tlck = txLock(tid, ip, mp, tlckDTREE | tlckNEW);
2564 dtlck = (struct dt_lock *) & tlck->lock;
2565
2566 ASSERT(dtlck->index == 0);
2567 lv = & dtlck->lv[0];
2568
2569
2570 pxd = &p->header.self;
2571 PXDaddress(pxd, nxaddr);
2572
2573
2574
2575
2576 lv->offset = 0;
2577 lv->length = p->header.maxslot;
2578 dtlck->index++;
2579
2580
2581 xsize = xlen << JFS_SBI(ip->i_sb)->l2bsize;
2582
2583
2584 DT_PUTPAGE(mp);
2585 jfs_info("dtRelocate: target dtpage relocated.");
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600 tlck = txMaplock(tid, ip, tlckDTREE | tlckFREE);
2601 pxdlock = (struct pxd_lock *) & tlck->lock;
2602 pxdlock->flag = mlckFREEPXD;
2603 PXDaddress(&pxdlock->pxd, oxaddr);
2604 PXDlength(&pxdlock->pxd, xlen);
2605 pxdlock->index = 1;
2606
2607
2608
2609
2610
2611
2612
2613 jfs_info("dtRelocate: update parent router entry.");
2614 tlck = txLock(tid, ip, pmp, tlckDTREE | tlckENTRY);
2615 dtlck = (struct dt_lock *) & tlck->lock;
2616 lv = & dtlck->lv[dtlck->index];
2617
2618
2619 stbl = DT_GETSTBL(pp);
2620 pxd = (pxd_t *) & pp->slot[stbl[index]];
2621 PXDaddress(pxd, nxaddr);
2622 lv->offset = stbl[index];
2623 lv->length = 1;
2624 dtlck->index++;
2625
2626
2627 DT_PUTPAGE(pmp);
2628
2629 return rc;
2630}
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643static int dtSearchNode(struct inode *ip, s64 lmxaddr, pxd_t * kpxd,
2644 struct btstack * btstack)
2645{
2646 int rc = 0;
2647 s64 bn;
2648 struct metapage *mp;
2649 dtpage_t *p;
2650 int psize = 288;
2651 s8 *stbl;
2652 int i;
2653 pxd_t *pxd;
2654 struct btframe *btsp;
2655
2656 BT_CLR(btstack);
2657
2658
2659
2660
2661
2662
2663 for (bn = 0;;) {
2664
2665 DT_GETPAGE(ip, bn, mp, psize, p, rc);
2666 if (rc)
2667 return rc;
2668
2669
2670
2671
2672 if (p->header.flag & BT_ROOT) {
2673 if (lmxaddr == 0)
2674 break;
2675 } else if (addressPXD(&p->header.self) == lmxaddr)
2676 break;
2677
2678
2679
2680
2681 if (p->header.flag & BT_LEAF) {
2682 DT_PUTPAGE(mp);
2683 return -ESTALE;
2684 }
2685
2686
2687 stbl = DT_GETSTBL(p);
2688 pxd = (pxd_t *) & p->slot[stbl[0]];
2689
2690
2691 bn = addressPXD(pxd);
2692 psize = lengthPXD(pxd) << JFS_SBI(ip->i_sb)->l2bsize;
2693
2694 DT_PUTPAGE(mp);
2695 }
2696
2697
2698
2699
2700 loop:
2701 stbl = DT_GETSTBL(p);
2702 for (i = 0; i < p->header.nextindex; i++) {
2703 pxd = (pxd_t *) & p->slot[stbl[i]];
2704
2705
2706 if (addressPXD(pxd) == addressPXD(kpxd) &&
2707 lengthPXD(pxd) == lengthPXD(kpxd)) {
2708 btsp = btstack->top;
2709 btsp->bn = bn;
2710 btsp->index = i;
2711 btsp->mp = mp;
2712
2713 return 0;
2714 }
2715 }
2716
2717
2718 if (p->header.next)
2719 bn = le64_to_cpu(p->header.next);
2720 else {
2721 DT_PUTPAGE(mp);
2722 return -ESTALE;
2723 }
2724
2725
2726 DT_PUTPAGE(mp);
2727
2728
2729 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
2730 if (rc)
2731 return rc;
2732
2733 goto loop;
2734}
2735#endif
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748static int dtRelink(tid_t tid, struct inode *ip, dtpage_t * p)
2749{
2750 int rc;
2751 struct metapage *mp;
2752 s64 nextbn, prevbn;
2753 struct tlock *tlck;
2754 struct dt_lock *dtlck;
2755 struct lv *lv;
2756
2757 nextbn = le64_to_cpu(p->header.next);
2758 prevbn = le64_to_cpu(p->header.prev);
2759
2760
2761 if (nextbn != 0) {
2762 DT_GETPAGE(ip, nextbn, mp, PSIZE, p, rc);
2763 if (rc)
2764 return rc;
2765
2766 BT_MARK_DIRTY(mp, ip);
2767
2768
2769
2770
2771
2772 tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK);
2773 jfs_info("dtRelink nextbn: tlck = 0x%p, ip = 0x%p, mp=0x%p",
2774 tlck, ip, mp);
2775 dtlck = (struct dt_lock *) & tlck->lock;
2776
2777
2778 if (dtlck->index >= dtlck->maxcnt)
2779 dtlck = (struct dt_lock *) txLinelock(dtlck);
2780 lv = & dtlck->lv[dtlck->index];
2781 lv->offset = 0;
2782 lv->length = 1;
2783 dtlck->index++;
2784
2785 p->header.prev = cpu_to_le64(prevbn);
2786 DT_PUTPAGE(mp);
2787 }
2788
2789
2790 if (prevbn != 0) {
2791 DT_GETPAGE(ip, prevbn, mp, PSIZE, p, rc);
2792 if (rc)
2793 return rc;
2794
2795 BT_MARK_DIRTY(mp, ip);
2796
2797
2798
2799
2800
2801 tlck = txLock(tid, ip, mp, tlckDTREE | tlckRELINK);
2802 jfs_info("dtRelink prevbn: tlck = 0x%p, ip = 0x%p, mp=0x%p",
2803 tlck, ip, mp);
2804 dtlck = (struct dt_lock *) & tlck->lock;
2805
2806
2807 if (dtlck->index >= dtlck->maxcnt)
2808 dtlck = (struct dt_lock *) txLinelock(dtlck);
2809 lv = & dtlck->lv[dtlck->index];
2810 lv->offset = 0;
2811 lv->length = 1;
2812 dtlck->index++;
2813
2814 p->header.next = cpu_to_le64(nextbn);
2815 DT_PUTPAGE(mp);
2816 }
2817
2818 return 0;
2819}
2820
2821
2822
2823
2824
2825
2826
2827void dtInitRoot(tid_t tid, struct inode *ip, u32 idotdot)
2828{
2829 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
2830 dtroot_t *p;
2831 int fsi;
2832 struct dtslot *f;
2833 struct tlock *tlck;
2834 struct dt_lock *dtlck;
2835 struct lv *lv;
2836 u16 xflag_save;
2837
2838
2839
2840
2841
2842 if (DO_INDEX(ip)) {
2843 if (!jfs_dirtable_inline(ip)) {
2844 struct tblock *tblk = tid_to_tblock(tid);
2845
2846
2847
2848
2849
2850
2851 xflag_save = tblk->xflag;
2852 tblk->xflag = 0;
2853
2854
2855
2856
2857
2858
2859
2860
2861 xtTruncate(tid, ip, 0, COMMIT_PWMAP);
2862 set_cflag(COMMIT_Stale, ip);
2863
2864 tblk->xflag = xflag_save;
2865 } else
2866 ip->i_size = 1;
2867
2868 jfs_ip->next_index = 2;
2869 } else
2870 ip->i_size = IDATASIZE;
2871
2872
2873
2874
2875
2876
2877 tlck = txLock(tid, ip, (struct metapage *) & jfs_ip->bxflag,
2878 tlckDTREE | tlckENTRY | tlckBTROOT);
2879 dtlck = (struct dt_lock *) & tlck->lock;
2880
2881
2882 ASSERT(dtlck->index == 0);
2883 lv = & dtlck->lv[0];
2884 lv->offset = 0;
2885 lv->length = DTROOTMAXSLOT;
2886 dtlck->index++;
2887
2888 p = &jfs_ip->i_dtroot;
2889
2890 p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;
2891
2892 p->header.nextindex = 0;
2893
2894
2895 fsi = 1;
2896 f = &p->slot[fsi];
2897
2898
2899 for (fsi++; fsi < DTROOTMAXSLOT; f++, fsi++)
2900 f->next = fsi;
2901 f->next = -1;
2902
2903 p->header.freelist = 1;
2904 p->header.freecnt = 8;
2905
2906
2907 p->header.idotdot = cpu_to_le32(idotdot);
2908
2909 return;
2910}
2911
2912
2913
2914
2915
2916
2917
2918
2919static void add_missing_indices(struct inode *inode, s64 bn)
2920{
2921 struct ldtentry *d;
2922 struct dt_lock *dtlck;
2923 int i;
2924 uint index;
2925 struct lv *lv;
2926 struct metapage *mp;
2927 dtpage_t *p;
2928 int rc;
2929 s8 *stbl;
2930 tid_t tid;
2931 struct tlock *tlck;
2932
2933 tid = txBegin(inode->i_sb, 0);
2934
2935 DT_GETPAGE(inode, bn, mp, PSIZE, p, rc);
2936
2937 if (rc) {
2938 printk(KERN_ERR "DT_GETPAGE failed!\n");
2939 goto end;
2940 }
2941 BT_MARK_DIRTY(mp, inode);
2942
2943 ASSERT(p->header.flag & BT_LEAF);
2944
2945 tlck = txLock(tid, inode, mp, tlckDTREE | tlckENTRY);
2946 if (BT_IS_ROOT(mp))
2947 tlck->type |= tlckBTROOT;
2948
2949 dtlck = (struct dt_lock *) &tlck->lock;
2950
2951 stbl = DT_GETSTBL(p);
2952 for (i = 0; i < p->header.nextindex; i++) {
2953 d = (struct ldtentry *) &p->slot[stbl[i]];
2954 index = le32_to_cpu(d->index);
2955 if ((index < 2) || (index >= JFS_IP(inode)->next_index)) {
2956 d->index = cpu_to_le32(add_index(tid, inode, bn, i));
2957 if (dtlck->index >= dtlck->maxcnt)
2958 dtlck = (struct dt_lock *) txLinelock(dtlck);
2959 lv = &dtlck->lv[dtlck->index];
2960 lv->offset = stbl[i];
2961 lv->length = 1;
2962 dtlck->index++;
2963 }
2964 }
2965
2966 DT_PUTPAGE(mp);
2967 (void) txCommit(tid, 1, &inode, 0);
2968end:
2969 txEnd(tid);
2970}
2971
2972
2973
2974
2975
2976struct jfs_dirent {
2977 loff_t position;
2978 int ino;
2979 u16 name_len;
2980 char name[0];
2981};
2982
2983
2984
2985
2986static inline struct jfs_dirent *next_jfs_dirent(struct jfs_dirent *dirent)
2987{
2988 return (struct jfs_dirent *)
2989 ((char *)dirent +
2990 ((sizeof (struct jfs_dirent) + dirent->name_len + 1 +
2991 sizeof (loff_t) - 1) &
2992 ~(sizeof (loff_t) - 1)));
2993}
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006int jfs_readdir(struct file *file, struct dir_context *ctx)
3007{
3008 struct inode *ip = file_inode(file);
3009 struct nls_table *codepage = JFS_SBI(ip->i_sb)->nls_tab;
3010 int rc = 0;
3011 loff_t dtpos;
3012 struct dtoffset {
3013 s16 pn;
3014 s16 index;
3015 s32 unused;
3016 } *dtoffset = (struct dtoffset *) &dtpos;
3017 s64 bn;
3018 struct metapage *mp;
3019 dtpage_t *p;
3020 int index;
3021 s8 *stbl;
3022 struct btstack btstack;
3023 int i, next;
3024 struct ldtentry *d;
3025 struct dtslot *t;
3026 int d_namleft, len, outlen;
3027 unsigned long dirent_buf;
3028 char *name_ptr;
3029 u32 dir_index;
3030 int do_index = 0;
3031 uint loop_count = 0;
3032 struct jfs_dirent *jfs_dirent;
3033 int jfs_dirents;
3034 int overflow, fix_page, page_fixed = 0;
3035 static int unique_pos = 2;
3036
3037 if (ctx->pos == DIREND)
3038 return 0;
3039
3040 if (DO_INDEX(ip)) {
3041
3042
3043
3044
3045
3046
3047 do_index = 1;
3048
3049 dir_index = (u32) ctx->pos;
3050
3051
3052
3053
3054
3055
3056 if (dir_index)
3057 dir_index--;
3058
3059 if (dir_index > 1) {
3060 struct dir_table_slot dirtab_slot;
3061
3062 if (dtEmpty(ip) ||
3063 (dir_index >= JFS_IP(ip)->next_index)) {
3064
3065 ctx->pos = DIREND;
3066 return 0;
3067 }
3068 repeat:
3069 rc = read_index(ip, dir_index, &dirtab_slot);
3070 if (rc) {
3071 ctx->pos = DIREND;
3072 return rc;
3073 }
3074 if (dirtab_slot.flag == DIR_INDEX_FREE) {
3075 if (loop_count++ > JFS_IP(ip)->next_index) {
3076 jfs_err("jfs_readdir detected infinite loop!");
3077 ctx->pos = DIREND;
3078 return 0;
3079 }
3080 dir_index = le32_to_cpu(dirtab_slot.addr2);
3081 if (dir_index == -1) {
3082 ctx->pos = DIREND;
3083 return 0;
3084 }
3085 goto repeat;
3086 }
3087 bn = addressDTS(&dirtab_slot);
3088 index = dirtab_slot.slot;
3089 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3090 if (rc) {
3091 ctx->pos = DIREND;
3092 return 0;
3093 }
3094 if (p->header.flag & BT_INTERNAL) {
3095 jfs_err("jfs_readdir: bad index table");
3096 DT_PUTPAGE(mp);
3097 ctx->pos = DIREND;
3098 return 0;
3099 }
3100 } else {
3101 if (dir_index == 0) {
3102
3103
3104
3105 ctx->pos = 1;
3106 if (!dir_emit(ctx, ".", 1, ip->i_ino, DT_DIR))
3107 return 0;
3108 }
3109
3110
3111
3112 ctx->pos = 2;
3113 if (!dir_emit(ctx, "..", 2, PARENT(ip), DT_DIR))
3114 return 0;
3115
3116
3117
3118
3119 if (dtEmpty(ip)) {
3120 ctx->pos = DIREND;
3121 return 0;
3122 }
3123
3124 if ((rc = dtReadFirst(ip, &btstack)))
3125 return rc;
3126
3127 DT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
3128 }
3129 } else {
3130
3131
3132
3133
3134
3135
3136
3137
3138 dtpos = ctx->pos;
3139 if (dtpos < 2) {
3140
3141 ctx->pos = 1;
3142 if (!dir_emit(ctx, ".", 1, ip->i_ino, DT_DIR))
3143 return 0;
3144 dtoffset->index = 2;
3145 ctx->pos = dtpos;
3146 }
3147
3148 if (dtoffset->pn == 0) {
3149 if (dtoffset->index == 2) {
3150
3151 if (!dir_emit(ctx, "..", 2, PARENT(ip), DT_DIR))
3152 return 0;
3153 } else {
3154 jfs_err("jfs_readdir called with invalid offset!");
3155 }
3156 dtoffset->pn = 1;
3157 dtoffset->index = 0;
3158 ctx->pos = dtpos;
3159 }
3160
3161 if (dtEmpty(ip)) {
3162 ctx->pos = DIREND;
3163 return 0;
3164 }
3165
3166 if ((rc = dtReadNext(ip, &ctx->pos, &btstack))) {
3167 jfs_err("jfs_readdir: unexpected rc = %d from dtReadNext",
3168 rc);
3169 ctx->pos = DIREND;
3170 return 0;
3171 }
3172
3173 DT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
3174
3175
3176 if (bn < 0) {
3177 ctx->pos = DIREND;
3178 return 0;
3179 }
3180 }
3181
3182 dirent_buf = __get_free_page(GFP_KERNEL);
3183 if (dirent_buf == 0) {
3184 DT_PUTPAGE(mp);
3185 jfs_warn("jfs_readdir: __get_free_page failed!");
3186 ctx->pos = DIREND;
3187 return -ENOMEM;
3188 }
3189
3190 while (1) {
3191 jfs_dirent = (struct jfs_dirent *) dirent_buf;
3192 jfs_dirents = 0;
3193 overflow = fix_page = 0;
3194
3195 stbl = DT_GETSTBL(p);
3196
3197 for (i = index; i < p->header.nextindex; i++) {
3198 d = (struct ldtentry *) & p->slot[stbl[i]];
3199
3200 if (((long) jfs_dirent + d->namlen + 1) >
3201 (dirent_buf + PAGE_SIZE)) {
3202
3203 index = i;
3204 overflow = 1;
3205 break;
3206 }
3207
3208 d_namleft = d->namlen;
3209 name_ptr = jfs_dirent->name;
3210 jfs_dirent->ino = le32_to_cpu(d->inumber);
3211
3212 if (do_index) {
3213 len = min(d_namleft, DTLHDRDATALEN);
3214 jfs_dirent->position = le32_to_cpu(d->index);
3215
3216
3217
3218
3219
3220
3221
3222 if ((jfs_dirent->position < 2) ||
3223 (jfs_dirent->position >=
3224 JFS_IP(ip)->next_index)) {
3225 if (!page_fixed && !isReadOnly(ip)) {
3226 fix_page = 1;
3227
3228
3229
3230
3231
3232
3233 overflow = 1;
3234 index = i;
3235 break;
3236 }
3237 jfs_dirent->position = unique_pos++;
3238 }
3239
3240
3241
3242
3243
3244 jfs_dirent->position++;
3245 } else {
3246 jfs_dirent->position = dtpos;
3247 len = min(d_namleft, DTLHDRDATALEN_LEGACY);
3248 }
3249
3250
3251 outlen = jfs_strfromUCS_le(name_ptr, d->name, len,
3252 codepage);
3253 jfs_dirent->name_len = outlen;
3254
3255
3256 next = d->next;
3257 while (next >= 0) {
3258 t = (struct dtslot *) & p->slot[next];
3259 name_ptr += outlen;
3260 d_namleft -= len;
3261
3262 if (d_namleft == 0) {
3263 jfs_error(ip->i_sb,
3264 "JFS:Dtree error: ino = %ld, bn=%lld, index = %d\n",
3265 (long)ip->i_ino,
3266 (long long)bn,
3267 i);
3268 goto skip_one;
3269 }
3270 len = min(d_namleft, DTSLOTDATALEN);
3271 outlen = jfs_strfromUCS_le(name_ptr, t->name,
3272 len, codepage);
3273 jfs_dirent->name_len += outlen;
3274
3275 next = t->next;
3276 }
3277
3278 jfs_dirents++;
3279 jfs_dirent = next_jfs_dirent(jfs_dirent);
3280skip_one:
3281 if (!do_index)
3282 dtoffset->index++;
3283 }
3284
3285 if (!overflow) {
3286
3287 if (p->header.flag & BT_ROOT)
3288 bn = 0;
3289 else {
3290 bn = le64_to_cpu(p->header.next);
3291 index = 0;
3292
3293 if (!do_index) {
3294 dtoffset->pn++;
3295 dtoffset->index = 0;
3296 }
3297 }
3298 page_fixed = 0;
3299 }
3300
3301
3302 DT_PUTPAGE(mp);
3303
3304 jfs_dirent = (struct jfs_dirent *) dirent_buf;
3305 while (jfs_dirents--) {
3306 ctx->pos = jfs_dirent->position;
3307 if (!dir_emit(ctx, jfs_dirent->name,
3308 jfs_dirent->name_len,
3309 jfs_dirent->ino, DT_UNKNOWN))
3310 goto out;
3311 jfs_dirent = next_jfs_dirent(jfs_dirent);
3312 }
3313
3314 if (fix_page) {
3315 add_missing_indices(ip, bn);
3316 page_fixed = 1;
3317 }
3318
3319 if (!overflow && (bn == 0)) {
3320 ctx->pos = DIREND;
3321 break;
3322 }
3323
3324 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3325 if (rc) {
3326 free_page(dirent_buf);
3327 return rc;
3328 }
3329 }
3330
3331 out:
3332 free_page(dirent_buf);
3333
3334 return rc;
3335}
3336
3337
3338
3339
3340
3341
3342
3343static int dtReadFirst(struct inode *ip, struct btstack * btstack)
3344{
3345 int rc = 0;
3346 s64 bn;
3347 int psize = 288;
3348 struct metapage *mp;
3349 dtpage_t *p;
3350 s8 *stbl;
3351 struct btframe *btsp;
3352 pxd_t *xd;
3353
3354 BT_CLR(btstack);
3355
3356
3357
3358
3359
3360
3361 for (bn = 0;;) {
3362 DT_GETPAGE(ip, bn, mp, psize, p, rc);
3363 if (rc)
3364 return rc;
3365
3366
3367
3368
3369 if (p->header.flag & BT_LEAF) {
3370
3371 btsp = btstack->top;
3372 btsp->bn = bn;
3373 btsp->index = 0;
3374 btsp->mp = mp;
3375
3376 return 0;
3377 }
3378
3379
3380
3381
3382 if (BT_STACK_FULL(btstack)) {
3383 DT_PUTPAGE(mp);
3384 jfs_error(ip->i_sb, "btstack overrun\n");
3385 BT_STACK_DUMP(btstack);
3386 return -EIO;
3387 }
3388
3389 BT_PUSH(btstack, bn, 0);
3390
3391
3392 stbl = DT_GETSTBL(p);
3393 xd = (pxd_t *) & p->slot[stbl[0]];
3394
3395
3396 bn = addressPXD(xd);
3397 psize = lengthPXD(xd) << JFS_SBI(ip->i_sb)->l2bsize;
3398
3399
3400 DT_PUTPAGE(mp);
3401 }
3402}
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415static int dtReadNext(struct inode *ip, loff_t * offset,
3416 struct btstack * btstack)
3417{
3418 int rc = 0;
3419 struct dtoffset {
3420 s16 pn;
3421 s16 index;
3422 s32 unused;
3423 } *dtoffset = (struct dtoffset *) offset;
3424 s64 bn;
3425 struct metapage *mp;
3426 dtpage_t *p;
3427 int index;
3428 int pn;
3429 s8 *stbl;
3430 struct btframe *btsp, *parent;
3431 pxd_t *xd;
3432
3433
3434
3435
3436 if ((rc = dtReadFirst(ip, btstack)))
3437 return rc;
3438
3439
3440 DT_GETSEARCH(ip, btstack->top, bn, mp, p, index);
3441
3442
3443 pn = dtoffset->pn - 1;
3444 index = dtoffset->index;
3445
3446
3447 if (pn == 0) {
3448
3449 if (index < p->header.nextindex)
3450 goto out;
3451
3452 if (p->header.flag & BT_ROOT) {
3453 bn = -1;
3454 goto out;
3455 }
3456
3457
3458 dtoffset->pn++;
3459 dtoffset->index = index = 0;
3460 goto a;
3461 }
3462
3463
3464 if (p->header.flag & BT_ROOT) {
3465 bn = -1;
3466 goto out;
3467 }
3468
3469
3470 if (pn > 1)
3471 goto b;
3472
3473
3474 a:
3475 bn = le64_to_cpu(p->header.next);
3476
3477
3478 DT_PUTPAGE(mp);
3479
3480
3481 if (bn == 0) {
3482 bn = -1;
3483 goto out;
3484 }
3485
3486 goto c;
3487
3488
3489
3490
3491 b:
3492
3493 DT_PUTPAGE(mp);
3494
3495
3496 btsp = btstack->top;
3497 parent = btsp - 1;
3498 bn = parent->bn;
3499 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3500 if (rc)
3501 return rc;
3502
3503
3504 while (pn >= p->header.nextindex) {
3505 pn -= p->header.nextindex;
3506
3507
3508 bn = le64_to_cpu(p->header.next);
3509
3510
3511 DT_PUTPAGE(mp);
3512
3513
3514 if (bn == 0) {
3515 bn = -1;
3516 goto out;
3517 }
3518
3519
3520 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3521 if (rc)
3522 return rc;
3523
3524
3525 parent->bn = bn;
3526 }
3527
3528
3529 stbl = DT_GETSTBL(p);
3530 xd = (pxd_t *) & p->slot[stbl[pn]];
3531 bn = addressPXD(xd);
3532
3533
3534 DT_PUTPAGE(mp);
3535
3536
3537
3538
3539 c:
3540 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3541 if (rc)
3542 return rc;
3543
3544
3545
3546
3547
3548 if (index >= p->header.nextindex) {
3549 bn = le64_to_cpu(p->header.next);
3550
3551
3552 DT_PUTPAGE(mp);
3553
3554
3555 if (bn == 0) {
3556 bn = -1;
3557 goto out;
3558 }
3559
3560
3561 DT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
3562 if (rc)
3563 return rc;
3564
3565
3566 dtoffset->pn++;
3567 dtoffset->index = 0;
3568 }
3569
3570 out:
3571
3572 btsp = btstack->top;
3573 btsp->bn = bn;
3574 btsp->index = dtoffset->index;
3575 btsp->mp = mp;
3576
3577 return 0;
3578}
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591static int dtCompare(struct component_name * key,
3592 dtpage_t * p,
3593 int si)
3594{
3595 wchar_t *kname;
3596 __le16 *name;
3597 int klen, namlen, len, rc;
3598 struct idtentry *ih;
3599 struct dtslot *t;
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617 kname = key->name;
3618 klen = key->namlen;
3619
3620 ih = (struct idtentry *) & p->slot[si];
3621 si = ih->next;
3622 name = ih->name;
3623 namlen = ih->namlen;
3624 len = min(namlen, DTIHDRDATALEN);
3625
3626
3627 len = min(klen, len);
3628 if ((rc = UniStrncmp_le(kname, name, len)))
3629 return rc;
3630
3631 klen -= len;
3632 namlen -= len;
3633
3634
3635 kname += len;
3636 while (klen > 0 && namlen > 0) {
3637
3638 t = (struct dtslot *) & p->slot[si];
3639 len = min(namlen, DTSLOTDATALEN);
3640 len = min(klen, len);
3641 name = t->name;
3642 if ((rc = UniStrncmp_le(kname, name, len)))
3643 return rc;
3644
3645 klen -= len;
3646 namlen -= len;
3647 kname += len;
3648 si = t->next;
3649 }
3650
3651 return (klen - namlen);
3652}
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667static int ciCompare(struct component_name * key,
3668 dtpage_t * p,
3669 int si,
3670 int flag)
3671{
3672 wchar_t *kname, x;
3673 __le16 *name;
3674 int klen, namlen, len, rc;
3675 struct ldtentry *lh;
3676 struct idtentry *ih;
3677 struct dtslot *t;
3678 int i;
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696 kname = key->name;
3697 klen = key->namlen;
3698
3699
3700
3701
3702 if (p->header.flag & BT_LEAF) {
3703 lh = (struct ldtentry *) & p->slot[si];
3704 si = lh->next;
3705 name = lh->name;
3706 namlen = lh->namlen;
3707 if (flag & JFS_DIR_INDEX)
3708 len = min(namlen, DTLHDRDATALEN);
3709 else
3710 len = min(namlen, DTLHDRDATALEN_LEGACY);
3711 }
3712
3713
3714
3715 else {
3716 ih = (struct idtentry *) & p->slot[si];
3717 si = ih->next;
3718 name = ih->name;
3719 namlen = ih->namlen;
3720 len = min(namlen, DTIHDRDATALEN);
3721 }
3722
3723
3724 len = min(klen, len);
3725 for (i = 0; i < len; i++, kname++, name++) {
3726
3727 if ((flag & JFS_OS2) == JFS_OS2)
3728 x = UniToupper(le16_to_cpu(*name));
3729 else
3730 x = le16_to_cpu(*name);
3731 if ((rc = *kname - x))
3732 return rc;
3733 }
3734
3735 klen -= len;
3736 namlen -= len;
3737
3738
3739 while (klen > 0 && namlen > 0) {
3740
3741 t = (struct dtslot *) & p->slot[si];
3742 len = min(namlen, DTSLOTDATALEN);
3743 len = min(klen, len);
3744 name = t->name;
3745 for (i = 0; i < len; i++, kname++, name++) {
3746
3747 if ((flag & JFS_OS2) == JFS_OS2)
3748 x = UniToupper(le16_to_cpu(*name));
3749 else
3750 x = le16_to_cpu(*name);
3751
3752 if ((rc = *kname - x))
3753 return rc;
3754 }
3755
3756 klen -= len;
3757 namlen -= len;
3758 si = t->next;
3759 }
3760
3761 return (klen - namlen);
3762}
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775static int ciGetLeafPrefixKey(dtpage_t * lp, int li, dtpage_t * rp,
3776 int ri, struct component_name * key, int flag)
3777{
3778 int klen, namlen;
3779 wchar_t *pl, *pr, *kname;
3780 struct component_name lkey;
3781 struct component_name rkey;
3782
3783 lkey.name = kmalloc_array(JFS_NAME_MAX + 1, sizeof(wchar_t),
3784 GFP_KERNEL);
3785 if (lkey.name == NULL)
3786 return -ENOMEM;
3787
3788 rkey.name = kmalloc_array(JFS_NAME_MAX + 1, sizeof(wchar_t),
3789 GFP_KERNEL);
3790 if (rkey.name == NULL) {
3791 kfree(lkey.name);
3792 return -ENOMEM;
3793 }
3794
3795
3796 dtGetKey(lp, li, &lkey, flag);
3797 lkey.name[lkey.namlen] = 0;
3798
3799 if ((flag & JFS_OS2) == JFS_OS2)
3800 ciToUpper(&lkey);
3801
3802 dtGetKey(rp, ri, &rkey, flag);
3803 rkey.name[rkey.namlen] = 0;
3804
3805
3806 if ((flag & JFS_OS2) == JFS_OS2)
3807 ciToUpper(&rkey);
3808
3809
3810 klen = 0;
3811 kname = key->name;
3812 namlen = min(lkey.namlen, rkey.namlen);
3813 for (pl = lkey.name, pr = rkey.name;
3814 namlen; pl++, pr++, namlen--, klen++, kname++) {
3815 *kname = *pr;
3816 if (*pl != *pr) {
3817 key->namlen = klen + 1;
3818 goto free_names;
3819 }
3820 }
3821
3822
3823 if (lkey.namlen < rkey.namlen) {
3824 *kname = *pr;
3825 key->namlen = klen + 1;
3826 } else
3827 key->namlen = klen;
3828
3829free_names:
3830 kfree(lkey.name);
3831 kfree(rkey.name);
3832 return 0;
3833}
3834
3835
3836
3837
3838
3839
3840
3841
3842static void dtGetKey(dtpage_t * p, int i,
3843 struct component_name * key, int flag)
3844{
3845 int si;
3846 s8 *stbl;
3847 struct ldtentry *lh;
3848 struct idtentry *ih;
3849 struct dtslot *t;
3850 int namlen, len;
3851 wchar_t *kname;
3852 __le16 *name;
3853
3854
3855 stbl = DT_GETSTBL(p);
3856 si = stbl[i];
3857 if (p->header.flag & BT_LEAF) {
3858 lh = (struct ldtentry *) & p->slot[si];
3859 si = lh->next;
3860 namlen = lh->namlen;
3861 name = lh->name;
3862 if (flag & JFS_DIR_INDEX)
3863 len = min(namlen, DTLHDRDATALEN);
3864 else
3865 len = min(namlen, DTLHDRDATALEN_LEGACY);
3866 } else {
3867 ih = (struct idtentry *) & p->slot[si];
3868 si = ih->next;
3869 namlen = ih->namlen;
3870 name = ih->name;
3871 len = min(namlen, DTIHDRDATALEN);
3872 }
3873
3874 key->namlen = namlen;
3875 kname = key->name;
3876
3877
3878
3879
3880 UniStrncpy_from_le(kname, name, len);
3881
3882
3883
3884
3885 while (si >= 0) {
3886
3887 t = &p->slot[si];
3888 kname += len;
3889 namlen -= len;
3890 len = min(namlen, DTSLOTDATALEN);
3891 UniStrncpy_from_le(kname, t->name, len);
3892
3893 si = t->next;
3894 }
3895}
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906static void dtInsertEntry(dtpage_t * p, int index, struct component_name * key,
3907 ddata_t * data, struct dt_lock ** dtlock)
3908{
3909 struct dtslot *h, *t;
3910 struct ldtentry *lh = NULL;
3911 struct idtentry *ih = NULL;
3912 int hsi, fsi, klen, len, nextindex;
3913 wchar_t *kname;
3914 __le16 *name;
3915 s8 *stbl;
3916 pxd_t *xd;
3917 struct dt_lock *dtlck = *dtlock;
3918 struct lv *lv;
3919 int xsi, n;
3920 s64 bn = 0;
3921 struct metapage *mp = NULL;
3922
3923 klen = key->namlen;
3924 kname = key->name;
3925
3926
3927 hsi = fsi = p->header.freelist;
3928 h = &p->slot[fsi];
3929 p->header.freelist = h->next;
3930 --p->header.freecnt;
3931
3932
3933 if (dtlck->index >= dtlck->maxcnt)
3934 dtlck = (struct dt_lock *) txLinelock(dtlck);
3935
3936 lv = & dtlck->lv[dtlck->index];
3937 lv->offset = hsi;
3938
3939
3940 if (p->header.flag & BT_LEAF) {
3941 lh = (struct ldtentry *) h;
3942 lh->next = h->next;
3943 lh->inumber = cpu_to_le32(data->leaf.ino);
3944 lh->namlen = klen;
3945 name = lh->name;
3946 if (data->leaf.ip) {
3947 len = min(klen, DTLHDRDATALEN);
3948 if (!(p->header.flag & BT_ROOT))
3949 bn = addressPXD(&p->header.self);
3950 lh->index = cpu_to_le32(add_index(data->leaf.tid,
3951 data->leaf.ip,
3952 bn, index));
3953 } else
3954 len = min(klen, DTLHDRDATALEN_LEGACY);
3955 } else {
3956 ih = (struct idtentry *) h;
3957 ih->next = h->next;
3958 xd = (pxd_t *) ih;
3959 *xd = data->xd;
3960 ih->namlen = klen;
3961 name = ih->name;
3962 len = min(klen, DTIHDRDATALEN);
3963 }
3964
3965 UniStrncpy_to_le(name, kname, len);
3966
3967 n = 1;
3968 xsi = hsi;
3969
3970
3971 t = h;
3972 klen -= len;
3973 while (klen) {
3974
3975 fsi = p->header.freelist;
3976 t = &p->slot[fsi];
3977 p->header.freelist = t->next;
3978 --p->header.freecnt;
3979
3980
3981 if (fsi != xsi + 1) {
3982
3983 lv->length = n;
3984 dtlck->index++;
3985
3986
3987 if (dtlck->index < dtlck->maxcnt)
3988 lv++;
3989 else {
3990 dtlck = (struct dt_lock *) txLinelock(dtlck);
3991 lv = & dtlck->lv[0];
3992 }
3993
3994 lv->offset = fsi;
3995 n = 0;
3996 }
3997
3998 kname += len;
3999 len = min(klen, DTSLOTDATALEN);
4000 UniStrncpy_to_le(t->name, kname, len);
4001
4002 n++;
4003 xsi = fsi;
4004 klen -= len;
4005 }
4006
4007
4008 lv->length = n;
4009 dtlck->index++;
4010
4011 *dtlock = dtlck;
4012
4013
4014 if (h == t) {
4015
4016 if (p->header.flag & BT_LEAF)
4017 lh->next = -1;
4018 else
4019 ih->next = -1;
4020 } else
4021
4022 t->next = -1;
4023
4024
4025 stbl = DT_GETSTBL(p);
4026 nextindex = p->header.nextindex;
4027 if (index < nextindex) {
4028 memmove(stbl + index + 1, stbl + index, nextindex - index);
4029
4030 if ((p->header.flag & BT_LEAF) && data->leaf.ip) {
4031 s64 lblock;
4032
4033
4034
4035
4036
4037 mp = NULL;
4038 for (n = index + 1; n <= nextindex; n++) {
4039 lh = (struct ldtentry *) & (p->slot[stbl[n]]);
4040 modify_index(data->leaf.tid, data->leaf.ip,
4041 le32_to_cpu(lh->index), bn, n,
4042 &mp, &lblock);
4043 }
4044 if (mp)
4045 release_metapage(mp);
4046 }
4047 }
4048
4049 stbl[index] = hsi;
4050
4051
4052 ++p->header.nextindex;
4053}
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064static void dtMoveEntry(dtpage_t * sp, int si, dtpage_t * dp,
4065 struct dt_lock ** sdtlock, struct dt_lock ** ddtlock,
4066 int do_index)
4067{
4068 int ssi, next;
4069 int di;
4070 int dsi;
4071 s8 *sstbl, *dstbl;
4072 int snamlen, len;
4073 struct ldtentry *slh, *dlh = NULL;
4074 struct idtentry *sih, *dih = NULL;
4075 struct dtslot *h, *s, *d;
4076 struct dt_lock *sdtlck = *sdtlock, *ddtlck = *ddtlock;
4077 struct lv *slv, *dlv;
4078 int xssi, ns, nd;
4079 int sfsi;
4080
4081 sstbl = (s8 *) & sp->slot[sp->header.stblindex];
4082 dstbl = (s8 *) & dp->slot[dp->header.stblindex];
4083
4084 dsi = dp->header.freelist;
4085 sfsi = sp->header.freelist;
4086
4087
4088 dlv = & ddtlck->lv[ddtlck->index];
4089 dlv->offset = dsi;
4090
4091
4092 slv = & sdtlck->lv[sdtlck->index];
4093 slv->offset = sstbl[si];
4094 xssi = slv->offset - 1;
4095
4096
4097
4098
4099 ns = nd = 0;
4100 for (di = 0; si < sp->header.nextindex; si++, di++) {
4101 ssi = sstbl[si];
4102 dstbl[di] = dsi;
4103
4104
4105 if (ssi != xssi + 1) {
4106
4107 slv->length = ns;
4108 sdtlck->index++;
4109
4110
4111 if (sdtlck->index < sdtlck->maxcnt)
4112 slv++;
4113 else {
4114 sdtlck = (struct dt_lock *) txLinelock(sdtlck);
4115 slv = & sdtlck->lv[0];
4116 }
4117
4118 slv->offset = ssi;
4119 ns = 0;
4120 }
4121
4122
4123
4124
4125
4126 h = d = &dp->slot[dsi];
4127
4128
4129 s = &sp->slot[ssi];
4130 if (sp->header.flag & BT_LEAF) {
4131
4132 slh = (struct ldtentry *) s;
4133 dlh = (struct ldtentry *) h;
4134 snamlen = slh->namlen;
4135
4136 if (do_index) {
4137 len = min(snamlen, DTLHDRDATALEN);
4138 dlh->index = slh->index;
4139 } else
4140 len = min(snamlen, DTLHDRDATALEN_LEGACY);
4141
4142 memcpy(dlh, slh, 6 + len * 2);
4143
4144 next = slh->next;
4145
4146
4147 dsi++;
4148 dlh->next = dsi;
4149 } else {
4150 sih = (struct idtentry *) s;
4151 snamlen = sih->namlen;
4152
4153 len = min(snamlen, DTIHDRDATALEN);
4154 dih = (struct idtentry *) h;
4155 memcpy(dih, sih, 10 + len * 2);
4156 next = sih->next;
4157
4158 dsi++;
4159 dih->next = dsi;
4160 }
4161
4162
4163 s->next = sfsi;
4164 s->cnt = 1;
4165 sfsi = ssi;
4166
4167 ns++;
4168 nd++;
4169 xssi = ssi;
4170
4171
4172
4173
4174 snamlen -= len;
4175 while ((ssi = next) >= 0) {
4176
4177 if (ssi != xssi + 1) {
4178
4179 slv->length = ns;
4180 sdtlck->index++;
4181
4182
4183 if (sdtlck->index < sdtlck->maxcnt)
4184 slv++;
4185 else {
4186 sdtlck =
4187 (struct dt_lock *)
4188 txLinelock(sdtlck);
4189 slv = & sdtlck->lv[0];
4190 }
4191
4192 slv->offset = ssi;
4193 ns = 0;
4194 }
4195
4196
4197 s = &sp->slot[ssi];
4198
4199
4200 d++;
4201
4202 len = min(snamlen, DTSLOTDATALEN);
4203 UniStrncpy_le(d->name, s->name, len);
4204
4205 ns++;
4206 nd++;
4207 xssi = ssi;
4208
4209 dsi++;
4210 d->next = dsi;
4211
4212
4213 next = s->next;
4214 s->next = sfsi;
4215 s->cnt = 1;
4216 sfsi = ssi;
4217
4218 snamlen -= len;
4219 }
4220
4221
4222 if (h == d) {
4223
4224 if (dp->header.flag & BT_LEAF)
4225 dlh->next = -1;
4226 else
4227 dih->next = -1;
4228 } else
4229
4230 d->next = -1;
4231 }
4232
4233
4234 slv->length = ns;
4235 sdtlck->index++;
4236 *sdtlock = sdtlck;
4237
4238 dlv->length = nd;
4239 ddtlck->index++;
4240 *ddtlock = ddtlck;
4241
4242
4243 sp->header.freelist = sfsi;
4244 sp->header.freecnt += nd;
4245
4246
4247 dp->header.nextindex = di;
4248
4249 dp->header.freelist = dsi;
4250 dp->header.freecnt -= nd;
4251}
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265static void dtDeleteEntry(dtpage_t * p, int fi, struct dt_lock ** dtlock)
4266{
4267 int fsi;
4268 s8 *stbl;
4269 struct dtslot *t;
4270 int si, freecnt;
4271 struct dt_lock *dtlck = *dtlock;
4272 struct lv *lv;
4273 int xsi, n;
4274
4275
4276 stbl = DT_GETSTBL(p);
4277 fsi = stbl[fi];
4278
4279
4280 if (dtlck->index >= dtlck->maxcnt)
4281 dtlck = (struct dt_lock *) txLinelock(dtlck);
4282 lv = & dtlck->lv[dtlck->index];
4283
4284 lv->offset = fsi;
4285
4286
4287 t = &p->slot[fsi];
4288 if (p->header.flag & BT_LEAF)
4289 si = ((struct ldtentry *) t)->next;
4290 else
4291 si = ((struct idtentry *) t)->next;
4292 t->next = si;
4293 t->cnt = 1;
4294
4295 n = freecnt = 1;
4296 xsi = fsi;
4297
4298
4299 while (si >= 0) {
4300
4301 if (si != xsi + 1) {
4302
4303 lv->length = n;
4304 dtlck->index++;
4305
4306
4307 if (dtlck->index < dtlck->maxcnt)
4308 lv++;
4309 else {
4310 dtlck = (struct dt_lock *) txLinelock(dtlck);
4311 lv = & dtlck->lv[0];
4312 }
4313
4314 lv->offset = si;
4315 n = 0;
4316 }
4317
4318 n++;
4319 xsi = si;
4320 freecnt++;
4321
4322 t = &p->slot[si];
4323 t->cnt = 1;
4324 si = t->next;
4325 }
4326
4327
4328 lv->length = n;
4329 dtlck->index++;
4330
4331 *dtlock = dtlck;
4332
4333
4334 t->next = p->header.freelist;
4335 p->header.freelist = fsi;
4336 p->header.freecnt += freecnt;
4337
4338
4339
4340
4341 si = p->header.nextindex;
4342 if (fi < si - 1)
4343 memmove(&stbl[fi], &stbl[fi + 1], si - fi - 1);
4344
4345 p->header.nextindex--;
4346}
4347
4348
4349
4350
4351
4352
4353
4354
4355
4356
4357
4358
4359
4360static void dtTruncateEntry(dtpage_t * p, int ti, struct dt_lock ** dtlock)
4361{
4362 int tsi;
4363 s8 *stbl;
4364 struct dtslot *t;
4365 int si, freecnt;
4366 struct dt_lock *dtlck = *dtlock;
4367 struct lv *lv;
4368 int fsi, xsi, n;
4369
4370
4371 stbl = DT_GETSTBL(p);
4372 tsi = stbl[ti];
4373
4374
4375 if (dtlck->index >= dtlck->maxcnt)
4376 dtlck = (struct dt_lock *) txLinelock(dtlck);
4377 lv = & dtlck->lv[dtlck->index];
4378
4379 lv->offset = tsi;
4380
4381
4382 t = &p->slot[tsi];
4383 ASSERT(p->header.flag & BT_INTERNAL);
4384 ((struct idtentry *) t)->namlen = 0;
4385 si = ((struct idtentry *) t)->next;
4386 ((struct idtentry *) t)->next = -1;
4387
4388 n = 1;
4389 freecnt = 0;
4390 fsi = si;
4391 xsi = tsi;
4392
4393
4394 while (si >= 0) {
4395
4396 if (si != xsi + 1) {
4397
4398 lv->length = n;
4399 dtlck->index++;
4400
4401
4402 if (dtlck->index < dtlck->maxcnt)
4403 lv++;
4404 else {
4405 dtlck = (struct dt_lock *) txLinelock(dtlck);
4406 lv = & dtlck->lv[0];
4407 }
4408
4409 lv->offset = si;
4410 n = 0;
4411 }
4412
4413 n++;
4414 xsi = si;
4415 freecnt++;
4416
4417 t = &p->slot[si];
4418 t->cnt = 1;
4419 si = t->next;
4420 }
4421
4422
4423 lv->length = n;
4424 dtlck->index++;
4425
4426 *dtlock = dtlck;
4427
4428
4429 if (freecnt == 0)
4430 return;
4431 t->next = p->header.freelist;
4432 p->header.freelist = fsi;
4433 p->header.freecnt += freecnt;
4434}
4435
4436
4437
4438
4439
4440static void dtLinelockFreelist(dtpage_t * p,
4441 int m,
4442 struct dt_lock ** dtlock)
4443{
4444 int fsi;
4445 struct dtslot *t;
4446 int si;
4447 struct dt_lock *dtlck = *dtlock;
4448 struct lv *lv;
4449 int xsi, n;
4450
4451
4452 fsi = p->header.freelist;
4453
4454
4455 if (dtlck->index >= dtlck->maxcnt)
4456 dtlck = (struct dt_lock *) txLinelock(dtlck);
4457 lv = & dtlck->lv[dtlck->index];
4458
4459 lv->offset = fsi;
4460
4461 n = 1;
4462 xsi = fsi;
4463
4464 t = &p->slot[fsi];
4465 si = t->next;
4466
4467
4468 while (si < m && si >= 0) {
4469
4470 if (si != xsi + 1) {
4471
4472 lv->length = n;
4473 dtlck->index++;
4474
4475
4476 if (dtlck->index < dtlck->maxcnt)
4477 lv++;
4478 else {
4479 dtlck = (struct dt_lock *) txLinelock(dtlck);
4480 lv = & dtlck->lv[0];
4481 }
4482
4483 lv->offset = si;
4484 n = 0;
4485 }
4486
4487 n++;
4488 xsi = si;
4489
4490 t = &p->slot[si];
4491 si = t->next;
4492 }
4493
4494
4495 lv->length = n;
4496 dtlck->index++;
4497
4498 *dtlock = dtlck;
4499}
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520int dtModify(tid_t tid, struct inode *ip,
4521 struct component_name * key, ino_t * orig_ino, ino_t new_ino, int flag)
4522{
4523 int rc;
4524 s64 bn;
4525 struct metapage *mp;
4526 dtpage_t *p;
4527 int index;
4528 struct btstack btstack;
4529 struct tlock *tlck;
4530 struct dt_lock *dtlck;
4531 struct lv *lv;
4532 s8 *stbl;
4533 int entry_si;
4534 struct ldtentry *entry;
4535
4536
4537
4538
4539
4540
4541 if ((rc = dtSearch(ip, key, orig_ino, &btstack, flag)))
4542 return rc;
4543
4544
4545 DT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
4546
4547 BT_MARK_DIRTY(mp, ip);
4548
4549
4550
4551 tlck = txLock(tid, ip, mp, tlckDTREE | tlckENTRY);
4552 dtlck = (struct dt_lock *) & tlck->lock;
4553
4554
4555 stbl = DT_GETSTBL(p);
4556 entry_si = stbl[index];
4557
4558
4559 ASSERT(dtlck->index == 0);
4560 lv = & dtlck->lv[0];
4561 lv->offset = entry_si;
4562 lv->length = 1;
4563 dtlck->index++;
4564
4565
4566 entry = (struct ldtentry *) & p->slot[entry_si];
4567
4568
4569 entry->inumber = cpu_to_le32(new_ino);
4570
4571
4572 DT_PUTPAGE(mp);
4573
4574 return 0;
4575}
4576