1 /*
2 * I/O for a Wiki document set.
3 *
4 * The files are kept in one flat directory.
5 * There are three files for each document:
6 * nnn - current version of the document
7 * nnn.hist - history (all old versions) of the document
8 * append-only
9 * L.nnn - write lock file for the document
10 *
11 * At the moment, since we don't have read/write locks
12 * in the file system, we use the L.nnn file as a read lock too.
13 * It's a hack but there aren't supposed to be many readers
14 * anyway.
15 *
16 * The nnn.hist file is in the format read by Brdwhist.
17 * The nnn file is in that format too, but only contains the
18 * last entry of the nnn.hist file.
19 *
20 * In addition to this set of files, there is an append-only
21 * map file that provides a mapping between numbers and titles.
22 * The map file is a sequence of lines of the form
23 * nnn Title Here
24 * The lock file L.map must be held to add to the end, to
25 * make sure that the numbers are allocated sequentially.
26 *
27 * We assume that writes to the map file will fit in one message,
28 * so that we don't have to read-lock the file.
29 */
30
31 #include <u.h>
32 #include <libc.h>
33 #include <bio.h>
34 #include <String.h>
35 #include <thread.h>
36 #include "wiki.h"
37
38 enum {
39 Nhash = 64,
40 Mcache = 128,
41 };
42
43 typedef struct Wcache Wcache;
44 struct Wcache {
45 int n;
46 ulong use;
47 RWLock;
48 ulong tcurrent;
49 ulong thist;
50 Whist *hist;
51 Whist *current;
52 Qid qid;
53 Qid qidhist;
54 Wcache *hash;
55 };
56
57 static RWLock cachelock;
58 static Wcache *tab[Nhash];
59 int ncache;
60
61 void
closewhist(Whist * wh)62 closewhist(Whist *wh)
63 {
64 int i;
65
66 if(wh && decref(wh) == 0){
67 free(wh->title);
68 for(i=0; i<wh->ndoc; i++){
69 free(wh->doc[i].author);
70 free(wh->doc[i].comment);
71 freepage(wh->doc[i].wtxt);
72 }
73 free(wh->doc);
74 free(wh);
75 }
76 }
77
78 void
freepage(Wpage * p)79 freepage(Wpage *p)
80 {
81 Wpage *next;
82
83 for(; p; p=next){
84 next = p->next;
85 free(p->text);
86 free(p->url);
87 free(p);
88 }
89 }
90
91 static Wcache*
findcache(int n)92 findcache(int n)
93 {
94 Wcache *w;
95
96 for(w=tab[n%Nhash]; w; w=w->hash)
97 if(w->n == n){
98 w->use = time(0);
99 return w;
100 }
101 return nil;
102 }
103
104 static int
getlock(char * lock)105 getlock(char *lock)
106 {
107 char buf[ERRMAX];
108 int i, fd;
109 enum { SECS = 200 };
110
111 for(i=0; i<SECS*10; i++){
112 fd = wcreate(lock, ORDWR, DMEXCL|0666);
113 if(fd >= 0)
114 return fd;
115 buf[0] = '\0';
116 rerrstr(buf, sizeof buf);
117 if(strstr(buf, "locked") == nil)
118 break;
119 sleep(1000/10);
120 }
121 werrstr("couldn't acquire lock %s: %r", lock);
122 return -1;
123 }
124
125 static Whist*
readwhist(char * file,char * lock,Qid * qid)126 readwhist(char *file, char *lock, Qid *qid)
127 {
128 int lfd;
129 Biobuf *b;
130 Dir *d;
131 Whist *wh;
132
133 if((lfd=getlock(lock)) < 0) // LOG?
134 return nil;
135
136 if(qid){
137 if((d = wdirstat(file)) == nil){
138 close(lfd);
139 return nil;
140 }
141 *qid = d->qid;
142 free(d);
143 }
144
145 if((b = wBopen(file, OREAD)) == nil){ //LOG?
146 close(lfd);
147 return nil;
148 }
149
150 wh = Brdwhist(b);
151
152 Bterm(b);
153 close(lfd);
154 return wh;
155 }
156
157 static void
gencurrent(Wcache * w,Qid * q,char * file,char * lock,ulong * t,Whist ** wp,int n)158 gencurrent(Wcache *w, Qid *q, char *file, char *lock, ulong *t, Whist **wp, int n)
159 {
160 Dir *d;
161 Whist *wh;
162
163 if(*wp && *t+Tcache >= time(0))
164 return;
165
166 wlock(w);
167 if(*wp && *t+Tcache >= time(0)){
168 wunlock(w);
169 return;
170 }
171
172 if(((d = wdirstat(file)) == nil) || (d->qid.path==q->path && d->qid.vers==q->vers)){
173 *t = time(0);
174 wunlock(w);
175 free(d);
176 return;
177 }
178
179 free(d);
180 if(wh = readwhist(file, lock, q)){
181 wh->n = n;
182 *t = time(0);
183 closewhist(*wp);
184 *wp = wh;
185 }
186 else fprint(2, "error file=%s lock=%s %r\n", file, lock);
187 wunlock(w);
188 }
189
190 static void
current(Wcache * w)191 current(Wcache *w)
192 {
193 char tmp[40];
194 char tmplock[40];
195
196 sprint(tmplock, "d/L.%d", w->n);
197 sprint(tmp, "d/%d", w->n);
198 gencurrent(w, &w->qid, tmp, tmplock, &w->tcurrent, &w->current, w->n);
199 }
200
201 static void
currenthist(Wcache * w)202 currenthist(Wcache *w)
203 {
204 char hist[40], lock[40];
205
206 sprint(hist, "d/%d.hist", w->n);
207 sprint(lock, "d/L.%d", w->n);
208
209 gencurrent(w, &w->qidhist, hist, lock, &w->thist, &w->hist, w->n);
210 }
211
212 void
voidcache(int n)213 voidcache(int n)
214 {
215 Wcache *c;
216
217 rlock(&cachelock);
218 if(c = findcache(n)){
219 wlock(c);
220 c->tcurrent = 0;
221 c->thist = 0;
222 /* aggressively free memory */
223 closewhist(c->hist);
224 c->hist = nil;
225 closewhist(c->current);
226 c->current = nil;
227 wunlock(c);
228 }
229 runlock(&cachelock);
230 }
231
232 static Whist*
getcache(int n,int hist)233 getcache(int n, int hist)
234 {
235 int i, isw;
236 ulong t;
237 Wcache *c, **cp, **evict;
238 Whist *wh;
239
240 isw = 0;
241 rlock(&cachelock);
242 if(c = findcache(n)){
243 Found:
244 current(c);
245 if(hist)
246 currenthist(c);
247 rlock(c);
248 if(hist)
249 wh = c->hist;
250 else
251 wh = c->current;
252 if(wh)
253 incref(wh);
254 runlock(c);
255 if(isw)
256 wunlock(&cachelock);
257 else
258 runlock(&cachelock);
259 return wh;
260 }
261 runlock(&cachelock);
262
263 wlock(&cachelock);
264 if(c = findcache(n)){
265 isw = 1; /* better to downgrade lock but can't */
266 goto Found;
267 }
268
269 if(ncache < Mcache){
270 Alloc:
271 c = emalloc(sizeof *c);
272 ncache++;
273 }else{
274 /* find something to evict. */
275 t = ~0;
276 evict = nil;
277 for(i=0; i<Nhash; i++){
278 for(cp=&tab[i], c=*cp; c; cp=&c->hash, c=*cp){
279 if(c->use < t
280 && (!c->hist || c->hist->ref==1)
281 && (!c->current || c->current->ref==1)){
282 evict = cp;
283 t = c->use;
284 }
285 }
286 }
287
288 if(evict == nil){
289 fprint(2, "wikifs: nothing to evict\n");
290 goto Alloc;
291 }
292
293 c = *evict;
294 *evict = c->hash;
295
296 closewhist(c->current);
297 closewhist(c->hist);
298 memset(c, 0, sizeof *c);
299 }
300
301 c->n = n;
302 c->hash = tab[n%Nhash];
303 tab[n%Nhash] = c;
304 isw = 1;
305 goto Found;
306 }
307
308 Whist*
getcurrent(int n)309 getcurrent(int n)
310 {
311 return getcache(n, 0);
312 }
313
314 Whist*
gethistory(int n)315 gethistory(int n)
316 {
317 return getcache(n, 1);
318 }
319
320 RWLock maplock;
321 Map *map;
322
323 static int
mapcmp(const void * va,const void * vb)324 mapcmp(const void *va, const void *vb)
325 {
326 Mapel *a, *b;
327
328 a = (Mapel*)va;
329 b = (Mapel*)vb;
330
331 return strcmp(a->s, b->s);
332 }
333
334 void
closemap(Map * m)335 closemap(Map *m)
336 {
337 if(decref(m)==0){
338 free(m->buf);
339 free(m->el);
340 free(m);
341 }
342 }
343
344 void
currentmap(int force)345 currentmap(int force)
346 {
347 char *p, *q, *r;
348 int lfd, fd, m, n;
349 Dir *d;
350 Map *nmap;
351 char *err = nil;
352
353 lfd = -1;
354 fd = -1;
355 d = nil;
356 nmap = nil;
357 if(!force && map && map->t+Tcache >= time(0))
358 return;
359
360 wlock(&maplock);
361 if(!force && map && map->t+Tcache >= time(0))
362 goto Return;
363
364 if((lfd = getlock("d/L.map")) < 0){
365 err = "can't lock";
366 goto Return;
367 }
368
369 if((d = wdirstat("d/map")) == nil)
370 goto Return;
371
372 if(map && d->qid.path == map->qid.path && d->qid.vers == map->qid.vers){
373 map->t = time(0);
374 goto Return;
375 }
376
377 if(d->length > Maxmap){
378 //LOG
379 err = "too long";
380 goto Return;
381 }
382
383 if((fd = wopen("d/map", OREAD)) < 0)
384 goto Return;
385
386 nmap = emalloc(sizeof *nmap);
387 nmap->buf = emalloc(d->length+1);
388 n = readn(fd, nmap->buf, d->length);
389 if(n != d->length){
390 err = "bad length";
391 goto Return;
392 }
393 nmap->buf[n] = '\0';
394
395 n = 0;
396 for(p=nmap->buf; p; p=strchr(p+1, '\n'))
397 n++;
398 nmap->el = emalloc(n*sizeof(nmap->el[0]));
399
400 m = 0;
401 for(p=nmap->buf; p && *p && m < n; p=q){
402 if(q = strchr(p+1, '\n'))
403 *q++ = '\0';
404 nmap->el[m].n = strtol(p, &r, 10);
405 if(*r == ' ')
406 r++;
407 else
408 {}//LOG?
409 nmap->el[m].s = strcondense(r, 1);
410 m++;
411 }
412 //LOG if m != n
413
414 nmap->qid = d->qid;
415 nmap->t = time(0);
416 nmap->nel = m;
417 qsort(nmap->el, nmap->nel, sizeof(nmap->el[0]), mapcmp);
418 if(map)
419 closemap(map);
420 map = nmap;
421 incref(map);
422 nmap = nil;
423
424 Return:
425 free(d);
426 if(nmap){
427 free(nmap->el);
428 free(nmap->buf);
429 free(nmap);
430 }
431 if(map == nil)
432 sysfatal("cannot get map: %s: %r", err);
433
434 if(fd >= 0)
435 close(fd);
436 if(lfd >= 0)
437 close(lfd);
438 wunlock(&maplock);
439 }
440
441 int
allocnum(char * title,int mustbenew)442 allocnum(char *title, int mustbenew)
443 {
444 char *p, *q;
445 int lfd, fd, n;
446 Biobuf b;
447
448 if(strcmp(title, "map")==0 || strcmp(title, "new")==0){
449 werrstr("reserved title name");
450 return -1;
451 }
452
453 if(title[0]=='\0' || strpbrk(title, "/<>:?")){
454 werrstr("invalid character in name");
455 return -1;
456 }
457 if((n = nametonum(title)) >= 0){
458 if(mustbenew){
459 werrstr("duplicate title");
460 return -1;
461 }
462 return n;
463 }
464
465 title = estrdup(title);
466 strcondense(title, 1);
467 strlower(title);
468 if(strchr(title, '\n') || strlen(title) > 200){
469 werrstr("bad title");
470 free(title);
471 return -1;
472 }
473
474 if((lfd = getlock("d/L.map")) < 0){
475 free(title);
476 return -1;
477 }
478
479 if((fd = wopen("d/map", ORDWR)) < 0){ // LOG?
480 close(lfd);
481 free(title);
482 return -1;
483 }
484
485 /*
486 * What we really need to do here is make sure the
487 * map is up-to-date, then make sure the title isn't
488 * taken, and then add it, all without dropping the locks.
489 *
490 * This turns out to be a mess when you start adding
491 * all the necessary dolock flags, so instead we just
492 * read through the file ourselves, and let our
493 * map catch up on its own.
494 */
495 Binit(&b, fd, OREAD);
496 n = 0;
497 while(p = Brdline(&b, '\n')){
498 p[Blinelen(&b)-1] = '\0';
499 n = atoi(p)+1;
500 q = strchr(p, ' ');
501 if(q == nil)
502 continue;
503 if(strcmp(q+1, title) == 0){
504 free(title);
505 close(fd);
506 close(lfd);
507 if(mustbenew){
508 werrstr("duplicate title");
509 return -1;
510 }else
511 return n;
512 }
513 }
514
515 seek(fd, 0, 2); /* just in case it's not append only */
516 fprint(fd, "%d %s\n", n, title);
517 close(fd);
518 close(lfd);
519 free(title);
520 /* kick the map */
521 currentmap(1);
522 return n;
523 }
524
525 int
nametonum(char * s)526 nametonum(char *s)
527 {
528 char *p;
529 int i, lo, hi, m, rv;
530
531 s = estrdup(s);
532 strlower(s);
533 for(p=s; *p; p++)
534 if(*p=='_')
535 *p = ' ';
536
537 currentmap(0);
538 rlock(&maplock);
539 lo = 0;
540 hi = map->nel;
541 while(hi-lo > 1){
542 m = (lo+hi)/2;
543 i = strcmp(s, map->el[m].s);
544 if(i < 0)
545 hi = m;
546 else
547 lo = m;
548 }
549 if(hi-lo == 1 && strcmp(s, map->el[lo].s)==0)
550 rv = map->el[lo].n;
551 else
552 rv = -1;
553 runlock(&maplock);
554 free(s);
555 return rv;
556 }
557
558 char*
numtoname(int n)559 numtoname(int n)
560 {
561 int i;
562 char *s;
563
564 currentmap(0);
565 rlock(&maplock);
566 for(i=0; i<map->nel; i++){
567 if(map->el[i].n==n)
568 break;
569 }
570 if(i==map->nel){
571 runlock(&maplock);
572 return nil;
573 }
574 s = estrdup(map->el[i].s);
575 runlock(&maplock);
576 return s;
577 }
578
579 Whist*
getcurrentbyname(char * s)580 getcurrentbyname(char *s)
581 {
582 int n;
583
584 if((n = nametonum(s)) < 0)
585 return nil;
586 return getcache(n, 0);
587 }
588
589 static String*
Brdstring(Biobuf * b)590 Brdstring(Biobuf *b)
591 {
592 long len;
593 String *s;
594 Dir *d;
595
596 d = dirfstat(Bfildes(b));
597 if (d == nil) /* shouldn't happen, we just opened it */
598 len = 0;
599 else
600 len = d->length;
601 free(d);
602 s = s_newalloc(len);
603 s_read(b, s, len);
604 return s;
605 }
606
607 /*
608 * Attempt to install a new page. If t==0 we are creating.
609 * Otherwise, we are editing and t must be set to the current
610 * version (t is the version we started with) to avoid conflicting
611 * writes.
612 *
613 * If there is a conflicting write, we still write the page to
614 * the history file, but mark it as a failed write.
615 */
616 int
writepage(int num,ulong t,String * s,char * title)617 writepage(int num, ulong t, String *s, char *title)
618 {
619 char tmp[40], tmplock[40], err[ERRMAX], hist[40], *p;
620 int conflict, lfd, fd;
621 Biobuf *b;
622 String *os;
623
624 sprint(tmp, "d/%d", num);
625 sprint(tmplock, "d/L.%d", num);
626 sprint(hist, "d/%d.hist", num);
627 if((lfd = getlock(tmplock)) < 0)
628 return -1;
629
630 conflict = 0;
631 if(b = wBopen(tmp, OREAD)){
632 Brdline(b, '\n'); /* title */
633 if(p = Brdline(b, '\n')) /* version */
634 p[Blinelen(b)-1] = '\0';
635 if(p==nil || p[0] != 'D'){
636 snprint(err, sizeof err, "bad format in extant file");
637 conflict = 1;
638 }else if(strtoul(p+1, 0, 0) != t){
639 os = Brdstring(b); /* why read the whole file? */
640 p = strchr(s_to_c(s), '\n');
641 if(p!=nil && strcmp(p+1, s_to_c(os))==0){ /* ignore dup write */
642 close(lfd);
643 s_free(os);
644 Bterm(b);
645 return 0;
646 }
647 s_free(os);
648 snprint(err, sizeof err, "update conflict %lud != %s", t, p+1);
649 conflict = 1;
650 }
651 Bterm(b);
652 }else{
653 if(t != 0){
654 close(lfd);
655 werrstr("did not expect to create");
656 return -1;
657 }
658 }
659
660 if((fd = wopen(hist, OWRITE)) < 0){
661 if((fd = wcreate(hist, OWRITE, 0666)) < 0){
662 close(lfd);
663 return -1;
664 }else
665 fprint(fd, "%s\n", title);
666 }
667 if(seek(fd, 0, 2) < 0
668 || (conflict && write(fd, "X\n", 2) != 2)
669 || write(fd, s_to_c(s), s_len(s)) != s_len(s)){
670 close(fd);
671 close(lfd);
672 return -1;
673 }
674 close(fd);
675
676 if(conflict){
677 close(lfd);
678 voidcache(num);
679 werrstr(err);
680 return -1;
681 }
682
683 if((fd = wcreate(tmp, OWRITE, 0666)) < 0){
684 close(lfd);
685 voidcache(num);
686 return -1;
687 }
688 if(write(fd, title, strlen(title)) != strlen(title)
689 || write(fd, "\n", 1) != 1
690 || write(fd, s_to_c(s), s_len(s)) != s_len(s)){
691 close(fd);
692 close(lfd);
693 voidcache(num);
694 return -1;
695 }
696 close(fd);
697 close(lfd);
698 voidcache(num);
699 return 0;
700 }
701