tfile.c - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
tfile.c (23784B)
---
1 /*
2 * Manage tree of VtFiles stored in the block cache.
3 *
4 * The single point of truth for the info about the VtFiles themselves
5 * is the block data. Because of this, there is no explicit locking of
6 * VtFile structures, and indeed there may be more than one VtFile
7 * structure for a given Venti file. They synchronize through the
8 * block cache.
9 *
10 * This is a bit simpler than fossil because there are no epochs
11 * or tags or anything else. Just mutable local blocks and immutable
12 * Venti blocks.
13 */
14
15 #include <u.h>
16 #include <libc.h>
17 #include <venti.h>
18
19 #define MaxBlock (1UL<<31)
20
21 static char ENotDir[] = "walk in non-directory";
22 static char ETooBig[] = "file too big";
23 /* static char EBadAddr[] = "bad address"; */
24 static char ELabelMismatch[] = "label mismatch";
25
26 static int sizetodepth(uvlong s, int psize, int dsize);
27 static VtBlock *fileload(VtFile *r, VtEntry *e);
28 static int shrinkdepth(VtFile*, VtBlock*, VtEntry*, int);
29 static int shrinksize(VtFile*, VtEntry*, uvlong);
30 static int growdepth(VtFile*, VtBlock*, VtEntry*, int);
31
32 #define ISLOCKED(r) ((r)->b != nil)
33 #define DEPTH(t) ((t)&VtTypeDepthMask)
34
35 static VtFile *
36 vtfilealloc(VtCache *c, VtBlock *b, VtFile *p, u32int offset, int mode)
37 {
38 int epb;
39 VtEntry e;
40 VtFile *r;
41
42 assert(p==nil || ISLOCKED(p));
43
44 if(p == nil){
45 assert(offset == 0);
46 epb = 1;
47 }else
48 epb = p->dsize / VtEntrySize;
49
50 if(b->type != VtDirType){
51 werrstr("bad block type %#uo", b->type);
52 return nil;
53 }
54
55 /*
56 * a non-active entry is the only thing that
57 * can legitimately happen here. all the others
58 * get prints.
59 */
60 if(vtentryunpack(&e, b->data, offset % epb) < 0){
61 fprint(2, "vtentryunpack failed: %r (%.*H)\n", VtEntrySize, b->data+VtEntrySize*(offset%epb));
62 return nil;
63 }
64 if(!(e.flags & VtEntryActive)){
65 werrstr("entry not active");
66 return nil;
67 }
68
69 if(DEPTH(e.type) < sizetodepth(e.size, e.psize, e.dsize)){
70 fprint(2, "depth %ud size %llud psize %lud dsize %lud\n",
71 DEPTH(e.type), e.size, e.psize, e.dsize);
72 werrstr("bad depth");
73 return nil;
74 }
75
76 r = vtmallocz(sizeof(VtFile));
77 r->c = c;
78 r->bsize = b->size;
79 r->mode = mode;
80 r->dsize = e.dsize;
81 r->psize = e.psize;
82 r->gen = e.gen;
83 r->dir = (e.type & VtTypeBaseMask) == VtDirType;
84 r->ref = 1;
85 r->parent = p;
86 if(p){
87 qlock(&p->lk);
88 assert(mode == VtOREAD || p->mode == VtORDWR);
89 p->ref++;
90 qunlock(&p->lk);
91 }else{
92 assert(b->addr != NilBlock);
93 r->local = 1;
94 }
95 memmove(r->score, b->score, VtScoreSize);
96 r->offset = offset;
97 r->epb = epb;
98
99 return r;
100 }
101
102 VtFile *
103 vtfileroot(VtCache *c, u32int addr, int mode)
104 {
105 VtFile *r;
106 VtBlock *b;
107
108 b = vtcachelocal(c, addr, VtDirType);
109 if(b == nil)
110 return nil;
111 r = vtfilealloc(c, b, nil, 0, mode);
112 vtblockput(b);
113 return r;
114 }
115
116 VtFile*
117 vtfileopenroot(VtCache *c, VtEntry *e)
118 {
119 VtBlock *b;
120 VtFile *f;
121
122 b = vtcacheallocblock(c, VtDirType, VtEntrySize);
123 if(b == nil)
124 return nil;
125
126 vtentrypack(e, b->data, 0);
127 f = vtfilealloc(c, b, nil, 0, VtORDWR);
128 vtblockput(b);
129 return f;
130 }
131
132 VtFile *
133 vtfilecreateroot(VtCache *c, int psize, int dsize, int type)
134 {
135 VtEntry e;
136
137 memset(&e, 0, sizeof e);
138 e.flags = VtEntryActive;
139 e.psize = psize;
140 e.dsize = dsize;
141 e.type = type;
142 memmove(e.score, vtzeroscore, VtScoreSize);
143
144 return vtfileopenroot(c, &e);
145 }
146
147 VtFile *
148 vtfileopen(VtFile *r, u32int offset, int mode)
149 {
150 ulong bn;
151 VtBlock *b;
152
153 assert(ISLOCKED(r));
154 if(!r->dir){
155 werrstr(ENotDir);
156 return nil;
157 }
158
159 bn = offset/(r->dsize/VtEntrySize);
160
161 b = vtfileblock(r, bn, mode);
162 if(b == nil)
163 return nil;
164 r = vtfilealloc(r->c, b, r, offset, mode);
165 vtblockput(b);
166 return r;
167 }
168
169 VtFile*
170 vtfilecreate(VtFile *r, int psize, int dsize, int type)
171 {
172 return _vtfilecreate(r, -1, psize, dsize, type);
173 }
174
175 VtFile*
176 _vtfilecreate(VtFile *r, int o, int psize, int dsize, int type)
177 {
178 int i;
179 VtBlock *b;
180 u32int bn, size;
181 VtEntry e;
182 int epb;
183 VtFile *rr;
184 u32int offset;
185
186 assert(ISLOCKED(r));
187 assert(type == VtDirType || type == VtDataType);
188
189 if(!r->dir){
190 werrstr(ENotDir);
191 return nil;
192 }
193
194 epb = r->dsize/VtEntrySize;
195
196 size = vtfilegetdirsize(r);
197 /*
198 * look at a random block to see if we can find an empty entry
199 */
200 if(o == -1){
201 offset = lnrand(size+1);
202 offset -= offset % epb;
203 }else
204 offset = o;
205
206 /* try the given block and then try the last block */
207 for(;;){
208 bn = offset/epb;
209 b = vtfileblock(r, bn, VtORDWR);
210 if(b == nil)
211 return nil;
212 for(i=offset%r->epb; i<epb; i++){
213 if(vtentryunpack(&e, b->data, i) < 0)
214 continue;
215 if((e.flags&VtEntryActive) == 0 && e.gen != ~0)
216 goto Found;
217 }
218 vtblockput(b);
219 if(offset == size){
220 fprint(2, "vtfilecreate: cannot happen\n");
221 werrstr("vtfilecreate: cannot happen");
222 return nil;
223 }
224 offset = size;
225 }
226
227 Found:
228 /* found an entry - gen already set */
229 e.psize = psize;
230 e.dsize = dsize;
231 e.flags = VtEntryActive;
232 e.type = type;
233 e.size = 0;
234 memmove(e.score, vtzeroscore, VtScoreSize);
235 vtentrypack(&e, b->data, i);
236
237 offset = bn*epb + i;
238 if(offset+1 > size){
239 if(vtfilesetdirsize(r, offset+1) < 0){
240 vtblockput(b);
241 return nil;
242 }
243 }
244
245 rr = vtfilealloc(r->c, b, r, offset, VtORDWR);
246 vtblockput(b);
247 return rr;
248 }
249
250 static int
251 vtfilekill(VtFile *r, int doremove)
252 {
253 VtEntry e;
254 VtBlock *b;
255
256 assert(ISLOCKED(r));
257 b = fileload(r, &e);
258 if(b == nil)
259 return -1;
260
261 if(doremove==0 && e.size == 0){
262 /* already truncated */
263 vtblockput(b);
264 return 0;
265 }
266
267 if(doremove){
268 if(e.gen != ~0)
269 e.gen++;
270 e.dsize = 0;
271 e.psize = 0;
272 e.flags = 0;
273 }else
274 e.flags &= ~VtEntryLocal;
275 e.type = 0;
276 e.size = 0;
277 memmove(e.score, vtzeroscore, VtScoreSize);
278 vtentrypack(&e, b->data, r->offset % r->epb);
279 vtblockput(b);
280
281 if(doremove){
282 vtfileunlock(r);
283 vtfileclose(r);
284 }
285
286 return 0;
287 }
288
289 int
290 vtfileremove(VtFile *r)
291 {
292 return vtfilekill(r, 1);
293 }
294
295 int
296 vtfiletruncate(VtFile *r)
297 {
298 return vtfilekill(r, 0);
299 }
300
301 uvlong
302 vtfilegetsize(VtFile *r)
303 {
304 VtEntry e;
305 VtBlock *b;
306
307 assert(ISLOCKED(r));
308 b = fileload(r, &e);
309 if(b == nil)
310 return ~(uvlong)0;
311 vtblockput(b);
312
313 return e.size;
314 }
315
316 static int
317 shrinksize(VtFile *r, VtEntry *e, uvlong size)
318 {
319 int i, depth, bsiz, type, isdir, ppb;
320 uvlong ptrsz;
321 uchar score[VtScoreSize];
322 VtBlock *b;
323
324 b = vtcacheglobal(r->c, e->score, e->type, r->dsize);
325 if(b == nil)
326 return -1;
327
328 ptrsz = e->dsize;
329 ppb = e->psize/VtScoreSize;
330 type = e->type;
331 depth = DEPTH(type);
332 for(i=0; i+1<depth; i++)
333 ptrsz *= ppb;
334
335 isdir = r->dir;
336 while(DEPTH(type) > 0){
337 if(b->addr == NilBlock){
338 /* not worth copying the block just so we can zero some of it */
339 vtblockput(b);
340 return -1;
341 }
342
343 /*
344 * invariant: each pointer in the tree rooted at b accounts for ptrsz bytes
345 */
346
347 /* zero the pointers to unnecessary blocks */
348 i = (size+ptrsz-1)/ptrsz;
349 for(; i<ppb; i++)
350 memmove(b->data+i*VtScoreSize, vtzeroscore, VtScoreSize);
351
352 /* recurse (go around again) on the partially necessary block */
353 i = size/ptrsz;
354 size = size%ptrsz;
355 if(size == 0){
356 vtblockput(b);
357 return 0;
358 }
359 ptrsz /= ppb;
360 type--;
361 memmove(score, b->data+i*VtScoreSize, VtScoreSize);
362 vtblockput(b);
363 if(type == VtDataType || type == VtDirType)
364 bsiz = r->dsize;
365 else
366 bsiz = r->psize;
367 b = vtcacheglobal(r->c, score, type, bsiz);
368 if(b == nil)
369 return -1;
370 }
371
372 if(b->addr == NilBlock){
373 vtblockput(b);
374 return -1;
375 }
376
377 /*
378 * No one ever truncates BtDir blocks.
379 */
380 if(depth==0 && !isdir && e->dsize > size)
381 memset(b->data+size, 0, e->dsize-size);
382 vtblockput(b);
383 return 0;
384 }
385
386 int
387 vtfilesetsize(VtFile *r, u64int size)
388 {
389 int depth, edepth;
390 VtEntry e;
391 VtBlock *b;
392
393 assert(ISLOCKED(r));
394 if(size == 0)
395 return vtfiletruncate(r);
396
397 if(size > VtMaxFileSize || size > ((uvlong)MaxBlock)*r->dsize){
398 werrstr(ETooBig);
399 return -1;
400 }
401
402 b = fileload(r, &e);
403 if(b == nil)
404 return -1;
405
406 /* quick out */
407 if(e.size == size){
408 vtblockput(b);
409 return 0;
410 }
411
412 depth = sizetodepth(size, e.psize, e.dsize);
413 edepth = DEPTH(e.type);
414 if(depth < edepth){
415 if(shrinkdepth(r, b, &e, depth) < 0){
416 vtblockput(b);
417 return -1;
418 }
419 }else if(depth > edepth){
420 if(growdepth(r, b, &e, depth) < 0){
421 vtblockput(b);
422 return -1;
423 }
424 }
425
426 if(size < e.size)
427 shrinksize(r, &e, size);
428
429 e.size = size;
430 vtentrypack(&e, b->data, r->offset % r->epb);
431 vtblockput(b);
432
433 return 0;
434 }
435
436 int
437 vtfilesetdirsize(VtFile *r, u32int ds)
438 {
439 uvlong size;
440 int epb;
441
442 assert(ISLOCKED(r));
443 epb = r->dsize/VtEntrySize;
444
445 size = (uvlong)r->dsize*(ds/epb);
446 size += VtEntrySize*(ds%epb);
447 return vtfilesetsize(r, size);
448 }
449
450 u32int
451 vtfilegetdirsize(VtFile *r)
452 {
453 ulong ds;
454 uvlong size;
455 int epb;
456
457 assert(ISLOCKED(r));
458 epb = r->dsize/VtEntrySize;
459
460 size = vtfilegetsize(r);
461 ds = epb*(size/r->dsize);
462 ds += (size%r->dsize)/VtEntrySize;
463 return ds;
464 }
465
466 int
467 vtfilegetentry(VtFile *r, VtEntry *e)
468 {
469 VtBlock *b;
470
471 assert(ISLOCKED(r));
472 b = fileload(r, e);
473 if(b == nil)
474 return -1;
475 vtblockput(b);
476
477 return 0;
478 }
479
480 int
481 vtfilesetentry(VtFile *r, VtEntry *e)
482 {
483 VtBlock *b;
484 VtEntry ee;
485
486 assert(ISLOCKED(r));
487 b = fileload(r, &ee);
488 if(b == nil)
489 return -1;
490 vtentrypack(e, b->data, r->offset % r->epb);
491 vtblockput(b);
492 return 0;
493 }
494
495 static VtBlock *
496 blockwalk(VtFile *r, VtBlock *p, int index, VtCache *c, int mode, VtEntry *e)
497 {
498 VtBlock *b;
499 int type, size;
500 uchar *score;
501
502 switch(p->type){
503 case VtDataType:
504 assert(0);
505 case VtDirType:
506 type = e->type;
507 score = e->score;
508 break;
509 default:
510 type = p->type - 1;
511 score = p->data+index*VtScoreSize;
512 break;
513 }
514 /*print("walk from %V/%d ty %d to %V ty %d\n", p->score, index, p->type, score, type); */
515
516 if(type == VtDirType || type == VtDataType)
517 size = r->dsize;
518 else
519 size = r->psize;
520 if(mode == VtOWRITE && vtglobaltolocal(score) == NilBlock){
521 b = vtcacheallocblock(c, type, size);
522 if(b)
523 goto HaveCopy;
524 }else
525 b = vtcacheglobal(c, score, type, size);
526
527 if(b == nil || mode == VtOREAD)
528 return b;
529
530 if(vtglobaltolocal(b->score) != NilBlock)
531 return b;
532
533 /*
534 * Copy on write.
535 */
536 e->flags |= VtEntryLocal;
537
538 b = vtblockcopy(b/*, e->tag, fs->ehi, fs->elo*/);
539 if(b == nil)
540 return nil;
541
542 HaveCopy:
543 if(p->type == VtDirType){
544 memmove(e->score, b->score, VtScoreSize);
545 vtentrypack(e, p->data, index);
546 }else{
547 memmove(p->data+index*VtScoreSize, b->score, VtScoreSize);
548 }
549 return b;
550 }
551
552 /*
553 * Change the depth of the VtFile r.
554 * The entry e for r is contained in block p.
555 */
556 static int
557 growdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
558 {
559 VtBlock *b, *bb;
560
561 assert(ISLOCKED(r));
562 assert(depth <= VtPointerDepth);
563
564 b = vtcacheglobal(r->c, e->score, e->type, r->dsize);
565 if(b == nil)
566 return -1;
567
568 /*
569 * Keep adding layers until we get to the right depth
570 * or an error occurs.
571 */
572 while(DEPTH(e->type) < depth){
573 bb = vtcacheallocblock(r->c, e->type+1, r->psize);
574 if(bb == nil)
575 break;
576 memmove(bb->data, b->score, VtScoreSize);
577 memmove(e->score, bb->score, VtScoreSize);
578 e->type++;
579 e->flags |= VtEntryLocal;
580 vtblockput(b);
581 b = bb;
582 }
583
584 vtentrypack(e, p->data, r->offset % r->epb);
585 vtblockput(b);
586
587 if(DEPTH(e->type) == depth)
588 return 0;
589 return -1;
590 }
591
592 static int
593 shrinkdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
594 {
595 VtBlock *b, *nb, *ob, *rb;
596
597 assert(ISLOCKED(r));
598 assert(depth <= VtPointerDepth);
599
600 rb = vtcacheglobal(r->c, e->score, e->type, r->psize);
601 if(rb == nil)
602 return -1;
603
604 /*
605 * Walk down to the new root block.
606 * We may stop early, but something is better than nothing.
607 */
608
609 ob = nil;
610 b = rb;
611 for(; DEPTH(e->type) > depth; e->type--){
612 nb = vtcacheglobal(r->c, b->data, e->type-1, r->psize);
613 if(nb == nil)
614 break;
615 if(ob!=nil && ob!=rb)
616 vtblockput(ob);
617 ob = b;
618 b = nb;
619 }
620
621 if(b == rb){
622 vtblockput(rb);
623 return 0;
624 }
625
626 /*
627 * Right now, e points at the root block rb, b is the new root block,
628 * and ob points at b. To update:
629 *
630 * (i) change e to point at b
631 * (ii) zero the pointer ob -> b
632 * (iii) free the root block
633 *
634 * p (the block containing e) must be written before
635 * anything else.
636 */
637
638 /* (i) */
639 memmove(e->score, b->score, VtScoreSize);
640 vtentrypack(e, p->data, r->offset % r->epb);
641
642 /* (ii) */
643 memmove(ob->data, vtzeroscore, VtScoreSize);
644
645 /* (iii) */
646 vtblockput(rb);
647 if(ob!=nil && ob!=rb)
648 vtblockput(ob);
649 vtblockput(b);
650
651 if(DEPTH(e->type) == depth)
652 return 0;
653 return -1;
654 }
655
656 static int
657 mkindices(VtEntry *e, u32int bn, int *index)
658 {
659 int i, np;
660
661 memset(index, 0, (VtPointerDepth+1)*sizeof(int));
662
663 np = e->psize/VtScoreSize;
664 for(i=0; bn > 0; i++){
665 if(i >= VtPointerDepth){
666 werrstr("bad address 0x%lux", (ulong)bn);
667 return -1;
668 }
669 index[i] = bn % np;
670 bn /= np;
671 }
672 return i;
673 }
674
675 VtBlock *
676 vtfileblock(VtFile *r, u32int bn, int mode)
677 {
678 VtBlock *b, *bb;
679 int index[VtPointerDepth+1];
680 VtEntry e;
681 int i;
682 int m;
683
684 assert(ISLOCKED(r));
685 assert(bn != NilBlock);
686
687 b = fileload(r, &e);
688 if(b == nil)
689 return nil;
690
691 i = mkindices(&e, bn, index);
692 if(i < 0)
693 goto Err;
694 if(i > DEPTH(e.type)){
695 if(mode == VtOREAD){
696 werrstr("bad address 0x%lux", (ulong)bn);
697 goto Err;
698 }
699 index[i] = 0;
700 if(growdepth(r, b, &e, i) < 0)
701 goto Err;
702 }
703
704 assert(b->type == VtDirType);
705
706 index[DEPTH(e.type)] = r->offset % r->epb;
707
708 /* mode for intermediate block */
709 m = mode;
710 if(m == VtOWRITE)
711 m = VtORDWR;
712
713 for(i=DEPTH(e.type); i>=0; i--){
714 bb = blockwalk(r, b, index[i], r->c, i==0 ? mode : m, &e);
715 if(bb == nil)
716 goto Err;
717 vtblockput(b);
718 b = bb;
719 }
720 b->pc = getcallerpc(&r);
721 return b;
722 Err:
723 vtblockput(b);
724 return nil;
725 }
726
727 int
728 vtfileblockscore(VtFile *r, u32int bn, uchar score[VtScoreSize])
729 {
730 VtBlock *b, *bb;
731 int index[VtPointerDepth+1];
732 VtEntry e;
733 int i;
734
735 assert(ISLOCKED(r));
736 assert(bn != NilBlock);
737
738 b = fileload(r, &e);
739 if(b == nil)
740 return -1;
741
742 if(DEPTH(e.type) == 0){
743 memmove(score, e.score, VtScoreSize);
744 vtblockput(b);
745 return 0;
746 }
747
748 i = mkindices(&e, bn, index);
749 if(i < 0){
750 vtblockput(b);
751 return -1;
752 }
753 if(i > DEPTH(e.type)){
754 memmove(score, vtzeroscore, VtScoreSize);
755 vtblockput(b);
756 return 0;
757 }
758
759 index[DEPTH(e.type)] = r->offset % r->epb;
760
761 for(i=DEPTH(e.type); i>=1; i--){
762 bb = blockwalk(r, b, index[i], r->c, VtOREAD, &e);
763 if(bb == nil)
764 goto Err;
765 vtblockput(b);
766 b = bb;
767 if(memcmp(b->score, vtzeroscore, VtScoreSize) == 0)
768 break;
769 }
770
771 memmove(score, b->data+index[0]*VtScoreSize, VtScoreSize);
772 vtblockput(b);
773 return 0;
774
775 Err:
776 vtblockput(b);
777 return -1;
778 }
779
780 void
781 vtfileincref(VtFile *r)
782 {
783 qlock(&r->lk);
784 r->ref++;
785 qunlock(&r->lk);
786 }
787
788 void
789 vtfileclose(VtFile *r)
790 {
791 if(r == nil)
792 return;
793 qlock(&r->lk);
794 r->ref--;
795 if(r->ref){
796 qunlock(&r->lk);
797 return;
798 }
799 assert(r->ref == 0);
800 qunlock(&r->lk);
801 if(r->parent)
802 vtfileclose(r->parent);
803 memset(r, ~0, sizeof(*r));
804 vtfree(r);
805 }
806
807 /*
808 * Retrieve the block containing the entry for r.
809 * If a snapshot has happened, we might need
810 * to get a new copy of the block. We avoid this
811 * in the common case by caching the score for
812 * the block and the last epoch in which it was valid.
813 *
814 * We use r->mode to tell the difference between active
815 * file system VtFiles (VtORDWR) and VtFiles for the
816 * snapshot file system (VtOREAD).
817 */
818 static VtBlock*
819 fileloadblock(VtFile *r, int mode)
820 {
821 char e[ERRMAX];
822 u32int addr;
823 VtBlock *b;
824
825 switch(r->mode){
826 default:
827 assert(0);
828 case VtORDWR:
829 assert(r->mode == VtORDWR);
830 if(r->local == 1){
831 b = vtcacheglobal(r->c, r->score, VtDirType, r->bsize);
832 if(b == nil)
833 return nil;
834 b->pc = getcallerpc(&r);
835 return b;
836 }
837 assert(r->parent != nil);
838 if(vtfilelock(r->parent, VtORDWR) < 0)
839 return nil;
840 b = vtfileblock(r->parent, r->offset/r->epb, VtORDWR);
841 vtfileunlock(r->parent);
842 if(b == nil)
843 return nil;
844 memmove(r->score, b->score, VtScoreSize);
845 r->local = 1;
846 return b;
847
848 case VtOREAD:
849 if(mode == VtORDWR){
850 werrstr("read/write lock of read-only file");
851 return nil;
852 }
853 addr = vtglobaltolocal(r->score);
854 if(addr == NilBlock)
855 return vtcacheglobal(r->c, r->score, VtDirType, r->bsize);
856
857 b = vtcachelocal(r->c, addr, VtDirType);
858 if(b)
859 return b;
860
861 /*
862 * If it failed because the epochs don't match, the block has been
863 * archived and reclaimed. Rewalk from the parent and get the
864 * new pointer. This can't happen in the VtORDWR case
865 * above because blocks in the current epoch don't get
866 * reclaimed. The fact that we're VtOREAD means we're
867 * a snapshot. (Or else the file system is read-only, but then
868 * the archiver isn't going around deleting blocks.)
869 */
870 rerrstr(e, sizeof e);
871 if(strcmp(e, ELabelMismatch) == 0){
872 if(vtfilelock(r->parent, VtOREAD) < 0)
873 return nil;
874 b = vtfileblock(r->parent, r->offset/r->epb, VtOREAD);
875 vtfileunlock(r->parent);
876 if(b){
877 fprint(2, "vtfilealloc: lost %V found %V\n",
878 r->score, b->score);
879 memmove(r->score, b->score, VtScoreSize);
880 return b;
881 }
882 }
883 return nil;
884 }
885 }
886
887 int
888 vtfilelock(VtFile *r, int mode)
889 {
890 VtBlock *b;
891
892 if(mode == -1)
893 mode = r->mode;
894
895 b = fileloadblock(r, mode);
896 if(b == nil)
897 return -1;
898 /*
899 * The fact that we are holding b serves as the
900 * lock entitling us to write to r->b.
901 */
902 assert(r->b == nil);
903 r->b = b;
904 b->pc = getcallerpc(&r);
905 return 0;
906 }
907
908 /*
909 * Lock two (usually sibling) VtFiles. This needs special care
910 * because the Entries for both vtFiles might be in the same block.
911 * We also try to lock blocks in left-to-right order within the tree.
912 */
913 int
914 vtfilelock2(VtFile *r, VtFile *rr, int mode)
915 {
916 VtBlock *b, *bb;
917
918 if(rr == nil)
919 return vtfilelock(r, mode);
920
921 if(mode == -1)
922 mode = r->mode;
923
924 if(r->parent==rr->parent && r->offset/r->epb == rr->offset/rr->epb){
925 b = fileloadblock(r, mode);
926 if(b == nil)
927 return -1;
928 vtblockduplock(b);
929 bb = b;
930 }else if(r->parent==rr->parent || r->offset > rr->offset){
931 bb = fileloadblock(rr, mode);
932 b = fileloadblock(r, mode);
933 }else{
934 b = fileloadblock(r, mode);
935 bb = fileloadblock(rr, mode);
936 }
937 if(b == nil || bb == nil){
938 if(b)
939 vtblockput(b);
940 if(bb)
941 vtblockput(bb);
942 return -1;
943 }
944
945 /*
946 * The fact that we are holding b and bb serves
947 * as the lock entitling us to write to r->b and rr->b.
948 */
949 r->b = b;
950 rr->b = bb;
951 b->pc = getcallerpc(&r);
952 bb->pc = getcallerpc(&r);
953 return 0;
954 }
955
956 void
957 vtfileunlock(VtFile *r)
958 {
959 VtBlock *b;
960
961 if(r->b == nil){
962 fprint(2, "vtfileunlock: already unlocked\n");
963 abort();
964 }
965 b = r->b;
966 r->b = nil;
967 vtblockput(b);
968 }
969
970 static VtBlock*
971 fileload(VtFile *r, VtEntry *e)
972 {
973 VtBlock *b;
974
975 assert(ISLOCKED(r));
976 b = r->b;
977 if(vtentryunpack(e, b->data, r->offset % r->epb) < 0)
978 return nil;
979 vtblockduplock(b);
980 return b;
981 }
982
983 static int
984 sizetodepth(uvlong s, int psize, int dsize)
985 {
986 int np;
987 int d;
988
989 /* determine pointer depth */
990 np = psize/VtScoreSize;
991 s = (s + dsize - 1)/dsize;
992 for(d = 0; s > 1; d++)
993 s = (s + np - 1)/np;
994 return d;
995 }
996
997 long
998 vtfileread(VtFile *f, void *data, long count, vlong offset)
999 {
1000 int frag;
1001 VtBlock *b;
1002 VtEntry e;
1003
1004 assert(ISLOCKED(f));
1005
1006 vtfilegetentry(f, &e);
1007 if(count == 0)
1008 return 0;
1009 if(count < 0 || offset < 0){
1010 werrstr("vtfileread: bad offset or count");
1011 return -1;
1012 }
1013 if(offset >= e.size)
1014 return 0;
1015
1016 if(offset+count > e.size)
1017 count = e.size - offset;
1018
1019 frag = offset % e.dsize;
1020 if(frag+count > e.dsize)
1021 count = e.dsize - frag;
1022
1023 b = vtfileblock(f, offset/e.dsize, VtOREAD);
1024 if(b == nil)
1025 return -1;
1026
1027 memmove(data, b->data+frag, count);
1028 vtblockput(b);
1029 return count;
1030 }
1031
1032 static long
1033 filewrite1(VtFile *f, void *data, long count, vlong offset)
1034 {
1035 int frag, m;
1036 VtBlock *b;
1037 VtEntry e;
1038
1039 vtfilegetentry(f, &e);
1040 if(count < 0 || offset < 0){
1041 werrstr("vtfilewrite: bad offset or count");
1042 return -1;
1043 }
1044
1045 frag = offset % e.dsize;
1046 if(frag+count > e.dsize)
1047 count = e.dsize - frag;
1048
1049 m = VtORDWR;
1050 if(frag == 0 && count == e.dsize)
1051 m = VtOWRITE;
1052
1053 b = vtfileblock(f, offset/e.dsize, m);
1054 if(b == nil)
1055 return -1;
1056
1057 memmove(b->data+frag, data, count);
1058 if(m == VtOWRITE && frag+count < e.dsize)
1059 memset(b->data+frag+count, 0, e.dsize-frag-count);
1060
1061 if(offset+count > e.size){
1062 vtfilegetentry(f, &e);
1063 e.size = offset+count;
1064 vtfilesetentry(f, &e);
1065 }
1066
1067 vtblockput(b);
1068 return count;
1069 }
1070
1071 long
1072 vtfilewrite(VtFile *f, void *data, long count, vlong offset)
1073 {
1074 long tot, m;
1075
1076 assert(ISLOCKED(f));
1077
1078 tot = 0;
1079 m = 0;
1080 while(tot < count){
1081 m = filewrite1(f, (char*)data+tot, count-tot, offset+tot);
1082 if(m <= 0)
1083 break;
1084 tot += m;
1085 }
1086 if(tot==0)
1087 return m;
1088 return tot;
1089 }
1090
1091 static int
1092 flushblock(VtCache *c, VtBlock *bb, uchar score[VtScoreSize], int ppb, int epb,
1093 int type)
1094 {
1095 u32int addr;
1096 VtBlock *b;
1097 VtEntry e;
1098 int i;
1099
1100 addr = vtglobaltolocal(score);
1101 if(addr == NilBlock)
1102 return 0;
1103
1104 if(bb){
1105 b = bb;
1106 if(memcmp(b->score, score, VtScoreSize) != 0)
1107 abort();
1108 }else
1109 if((b = vtcachelocal(c, addr, type)) == nil)
1110 return -1;
1111
1112 switch(type){
1113 case VtDataType:
1114 break;
1115
1116 case VtDirType:
1117 for(i=0; i<epb; i++){
1118 if(vtentryunpack(&e, b->data, i) < 0)
1119 goto Err;
1120 if(!(e.flags&VtEntryActive))
1121 continue;
1122 if(flushblock(c, nil, e.score, e.psize/VtScoreSize, e.dsize/VtEntrySize,
1123 e.type) < 0)
1124 goto Err;
1125 vtentrypack(&e, b->data, i);
1126 }
1127 break;
1128
1129 default: /* VtPointerTypeX */
1130 for(i=0; i<ppb; i++){
1131 if(flushblock(c, nil, b->data+VtScoreSize*i, ppb, epb, type-1) < 0)
1132 goto Err;
1133 }
1134 break;
1135 }
1136
1137 if(vtblockwrite(b) < 0)
1138 goto Err;
1139 memmove(score, b->score, VtScoreSize);
1140 if(b != bb)
1141 vtblockput(b);
1142 return 0;
1143
1144 Err:
1145 if(b != bb)
1146 vtblockput(b);
1147 return -1;
1148 }
1149
1150 int
1151 vtfileflush(VtFile *f)
1152 {
1153 int ret;
1154 VtBlock *b;
1155 VtEntry e;
1156
1157 assert(ISLOCKED(f));
1158 b = fileload(f, &e);
1159 if(!(e.flags&VtEntryLocal)){
1160 vtblockput(b);
1161 return 0;
1162 }
1163
1164 ret = flushblock(f->c, nil, e.score, e.psize/VtScoreSize, e.dsize/VtEntrySize,
1165 e.type);
1166 if(ret < 0){
1167 vtblockput(b);
1168 return -1;
1169 }
1170
1171 vtentrypack(&e, b->data, f->offset % f->epb);
1172 vtblockput(b);
1173 return 0;
1174 }
1175
1176 int
1177 vtfileflushbefore(VtFile *r, u64int offset)
1178 {
1179 VtBlock *b, *bb;
1180 VtEntry e;
1181 int i, base, depth, ppb, epb, doflush;
1182 int index[VtPointerDepth+1], j, ret;
1183 VtBlock *bi[VtPointerDepth+2];
1184 uchar *score;
1185
1186 assert(ISLOCKED(r));
1187 if(offset == 0)
1188 return 0;
1189
1190 b = fileload(r, &e);
1191 if(b == nil)
1192 return -1;
1193
1194 /*
1195 * compute path through tree for the last written byte and the next one.
1196 */
1197 ret = -1;
1198 memset(bi, 0, sizeof bi);
1199 depth = DEPTH(e.type);
1200 bi[depth+1] = b;
1201 i = mkindices(&e, (offset-1)/e.dsize, index);
1202 if(i < 0)
1203 goto Err;
1204 if(i > depth)
1205 goto Err;
1206 ppb = e.psize / VtScoreSize;
1207 epb = e.dsize / VtEntrySize;
1208
1209 /*
1210 * load the blocks along the last written byte
1211 */
1212 index[depth] = r->offset % r->epb;
1213 for(i=depth; i>=0; i--){
1214 bb = blockwalk(r, b, index[i], r->c, VtORDWR, &e);
1215 if(bb == nil)
1216 goto Err;
1217 bi[i] = bb;
1218 b = bb;
1219 }
1220 ret = 0;
1221
1222 /*
1223 * walk up the path from leaf to root, flushing anything that
1224 * has been finished.
1225 */
1226 base = e.type&~VtTypeDepthMask;
1227 for(i=0; i<=depth; i++){
1228 doflush = 0;
1229 if(i == 0){
1230 /* leaf: data or dir block */
1231 if(offset%e.dsize == 0)
1232 doflush = 1;
1233 }else{
1234 /*
1235 * interior node: pointer blocks.
1236 * specifically, b = bi[i] is a block whose index[i-1]'th entry
1237 * points at bi[i-1].
1238 */
1239 b = bi[i];
1240
1241 /*
1242 * the index entries up to but not including index[i-1] point at
1243 * finished blocks, so flush them for sure.
1244 */
1245 for(j=0; j<index[i-1]; j++)
1246 if(flushblock(r->c, nil, b->data+j*VtScoreSize, ppb, epb, base+i-1) < 0)
1247 goto Err;
1248
1249 /*
1250 * if index[i-1] is the last entry in the block and is global
1251 * (i.e. the kid is flushed), then we can flush this block.
1252 */
1253 if(j==ppb-1 && vtglobaltolocal(b->data+j*VtScoreSize)==NilBlock)
1254 doflush = 1;
1255 }
1256 if(doflush){
1257 if(i == depth)
1258 score = e.score;
1259 else
1260 score = bi[i+1]->data+index[i]*VtScoreSize;
1261 if(flushblock(r->c, bi[i], score, ppb, epb, base+i) < 0)
1262 goto Err;
1263 }
1264 }
1265
1266 Err:
1267 /* top: entry. do this always so that the score is up-to-date */
1268 vtentrypack(&e, bi[depth+1]->data, index[depth]);
1269 for(i=0; i<nelem(bi); i++)
1270 if(bi[i])
1271 vtblockput(bi[i]);
1272 return ret;
1273 }