1 /* BLURB lgpl
2
3 Coda File System
4 Release 5
5
6 Copyright (c) 1987-2016 Carnegie Mellon University
7 Additional copyrights listed below
8
9 This code is distributed "AS IS" without warranty of any kind under
10 the terms of the GNU Library General Public Licence Version 2, as
11 shown in the file LICENSE. The technical and financial contributors to
12 Coda are listed in the file CREDITS.
13
14 Additional copyrights
15 none currently
16
17 #*/
18
19 /*
20 *
21 * RVM internal structure support functions
22 *
23 * * Doubly linked list and free list functions
24 * * RVM structures cache
25 * * Initializers, Copiers, and Finalizers for RVM exported
26 * structures.
27 * * RW_lock functions
28 *
29 */
30
31 #ifdef HAVE_CONFIG_H
32 #include <config.h>
33 #endif
34
35 #if defined(hpux) || defined(__hpux)
36 #include <hp_bsd.h>
37 #endif /* hpux */
38 #include <unistd.h>
39 #include <stdlib.h>
40 #include <stdio.h>
41 #include <sys/time.h>
42 #include "rvm_private.h"
43
44 /* globals */
45
46 extern rvm_length_t page_size;
47 extern rvm_length_t page_mask;
48 extern char *rvm_errmsg; /* internal error message buffer */
49 extern rvm_length_t rvm_optimizations; /* optimization switches */
50 /* locals */
51
52 /* locks for free lists */
53 RVM_MUTEX free_lists_locks[NUM_CACHE_TYPES];
54
55 /* creation count vector for instances of internal types */
56 long type_counts[NUM_CACHE_TYPES];
57
58 /* free list vector for internal types */
59 list_entry_t free_lists[NUM_CACHE_TYPES];
60
61 /* preallocation count vector for internal types free lists */
62 long pre_alloc[NUM_CACHE_TYPES] = {NUM_PRE_ALLOCATED};
63
64 /* allocation cache maximum counts */
65 long max_alloc[NUM_CACHE_TYPES] = {MAX_ALLOCATED};
66
67 /* internal structure size vector for generic list allocations */
68 long cache_type_sizes[NUM_CACHE_TYPES] = {CACHE_TYPE_SIZES};
69
70 #ifndef ZERO
71 #define ZERO 0
72 #endif
73
74 /* forward decls */
75 static void clear_tree_root(tree_root_t *root);
76 static void rw_lock_clear(rw_lock_t *rwl);
77
78 /* initialization lock & flag */
79 /* cannot be statically allocated if using pthreads */
80 static RVM_MUTEX free_lists_init_lock = MUTEX_INITIALIZER;
81 static rvm_bool_t free_lists_inited = rvm_false;
82 /* Routines to allocate and manipulate the doubly-linked circular lists
83 used in RVM (derived from rpc2 routines)
84
85 List headers always use the list_entry_t structure and maintain a count of
86 elements on the list. Headers can be statically or dynamically allocated,
87 but must be initialized with init_list_header before use.
88 */
89 /* routine to initialize a list header
90 can be statically or dynamically allocated
91 */
init_list_header(whichlist,struct_id)92 void init_list_header(whichlist,struct_id)
93 list_entry_t *whichlist; /* pointer to list header */
94 struct_id_t struct_id; /* list type */
95 {
96 whichlist->nextentry = whichlist; /* pointers are to self now */
97 whichlist->preventry = whichlist;
98 whichlist->struct_id = struct_id; /* set the type */
99 whichlist->list.length = 0; /* list is empty */
100 whichlist->is_hdr = rvm_true; /* mark header */
101 }
102
103 /* routine to allocate typed list cells
104 creates 1 entry of id type & returns address of cell
105 */
malloc_list_entry(id)106 static list_entry_t *malloc_list_entry(id)
107 struct_id_t id;
108 {
109 register list_entry_t *cell;
110
111 /* allocate the element */
112 cell = (list_entry_t *) calloc(1, cache_type_sizes[ID_INDEX(id)]);
113 assert(cell != NULL);
114 type_counts[ID_INDEX(id)] ++; /* count allocations */
115
116 cell->struct_id = id; /* cell type */
117 cell->is_hdr = rvm_false; /* is not a header */
118
119 return cell;
120 }
121 /* generic routine to move elements between lists
122 the types of lists must be the same if both from & to ptrs are not null.
123 if cell is NULL, the 1st entry in fromptr list is selected
124 if fromptr is NULL, victim must not be NULL.
125 if fromptr is not null, from->list.length is decremented.
126 if toptr is not null, victim is appended & to->list.length is incremented.
127 in all cases a pointer to the moved entry is returned.
128 */
move_list_entry(fromptr,toptr,victim)129 list_entry_t *move_list_entry(fromptr, toptr, victim)
130 register list_entry_t *fromptr; /* from list header */
131 register list_entry_t *toptr; /* to list header */
132 register list_entry_t *victim; /* pointer to entry to be moved */
133 {
134
135 if (!fromptr && victim)
136 fromptr = victim->list.name;
137
138 if (fromptr)
139 {
140 assert(fromptr->is_hdr);
141 if ((victim == NULL) && LIST_EMPTY((*fromptr)))
142 victim = malloc_list_entry(fromptr->struct_id);
143 else
144 {
145 if (victim == NULL) /* choose 1st if no victim */
146 victim = fromptr->nextentry;
147 assert(!victim->is_hdr);
148 assert(victim->list.name == fromptr);
149 /* remque((void *)victim); */ /* unlink from first list */
150 if (victim->nextentry)
151 victim->nextentry->preventry = victim->preventry;
152 if (victim->preventry)
153 victim->preventry->nextentry = victim->nextentry;
154 victim->nextentry = victim->preventry = NULL;
155
156 fromptr->list.length --;
157 }
158 }
159 else
160 {
161 assert(victim != NULL);
162 assert(!victim->is_hdr);
163 assert(toptr != NULL);
164 }
165
166 if (toptr != NULL)
167 {
168 assert(toptr->is_hdr);
169 assert(victim->struct_id == toptr->struct_id);
170 victim->list.name = toptr;
171 /* insque((void *)victim,(void *)toptr->preventry); */ /* insert at tail of second list */
172 victim->preventry = toptr->preventry;
173 victim->nextentry = toptr;
174 victim->preventry->nextentry = toptr->preventry = victim;
175
176 toptr->list.length ++;
177 }
178 else victim->list.name = NULL;
179
180 return victim;
181 }
182 /* internal types free lists support */
183
184 /* initialization -- call once at initialization
185 free lists will be initialized and be pre-allocated with the number of
186 elements specified in NUM_PRE_ALLOCATED (from rvm_private.h)
187 */
init_free_lists()188 static void init_free_lists()
189 {
190 list_entry_t *cell;
191 int i,j;
192
193 assert(!free_lists_inited);
194 for (i = 0; i < ID_INDEX(struct_last_cache_id); i++)
195 {
196 init_list_header(&free_lists[i],INDEX_ID(i));
197 mutex_init(&free_lists_locks[i]);
198 for (j = 0; j < pre_alloc[i]; j++)
199 {
200 cell = malloc_list_entry(INDEX_ID(i));
201 assert(cell != NULL);
202 (void)move_list_entry(NULL,&free_lists[i],cell);
203 }
204 }
205 }
206
207 /* get a cell from free list */
alloc_list_entry(id)208 list_entry_t *alloc_list_entry(id)
209 struct_id_t id;
210 {
211 list_entry_t *cell;
212
213 assert((((long)id > (long)struct_first_id) &&
214 ((long)id < (long)struct_last_cache_id)));
215
216 CRITICAL(free_lists_locks[ID_INDEX(id)],
217 {
218 cell = move_list_entry(&free_lists[ID_INDEX(id)],
219 NULL,NULL);
220 });
221
222 return cell;
223 }
224 /* kill cell */
kill_list_entry(cell)225 static void kill_list_entry(cell)
226 list_entry_t *cell;
227 {
228 assert(cell != NULL);
229
230 /* unlink from present list */
231 if (cell->list.name)
232 (void)move_list_entry(NULL, NULL, cell);
233
234 /* terminate with extreme prejudice */
235 type_counts[ID_INDEX(cell->struct_id)] --;
236 free((char *)cell);
237 }
238
239 /* move cell to free list
240 will remove cell from any list that it is on before freeing
241 */
free_list_entry(cell)242 static void free_list_entry(cell)
243 register list_entry_t *cell;
244 {
245 int id_index;
246 assert(cell != NULL);
247 assert((((long)cell->struct_id>(long)struct_first_id) &&
248 ((long)cell->struct_id<(long)struct_last_cache_id)));
249
250
251 id_index = ID_INDEX(cell->struct_id);
252 CRITICAL(free_lists_locks[id_index],
253 { /* begin free_list_lock crit sec */
254 if (max_alloc[id_index] >
255 free_lists[id_index].list.length)
256 {
257 /* move to appropriate free list */
258 (void)move_list_entry(cell->list.name,
259 &free_lists[id_index],
260 cell);
261 }
262 else
263 /* kill if enough of this type cached */
264 kill_list_entry(cell);
265 }); /* end free_list_lock crit sec */
266 }
267 #ifdef UNUSED
268 /* clear free lists */
clear_free_list(id)269 void clear_free_list(id)
270 struct_id_t id; /* type of free list */
271 {
272 list_entry_t *cell;
273
274 CRITICAL(free_lists_locks[ID_INDEX(id)],
275 { /* begin free_list_lock crit sec */
276 while (LIST_NOT_EMPTY(free_lists[ID_INDEX(id)]))
277 {
278 cell = free_lists[ID_INDEX(id)].nextentry;
279 kill_list_entry(cell);
280 }
281 }); /* end free_list_lock crit sec */
282 }
283
clear_free_lists()284 void clear_free_lists()
285 {
286 int i;
287
288 for (i = 0; i < ID_INDEX(struct_last_cache_id); i++)
289 clear_free_list(INDEX_ID(i));
290 }
291 #endif
292 /* unique name generator */
293 /* Cannot be statically allocated in pthreads */
294 static RVM_MUTEX uname_lock = MUTEX_INITIALIZER;
295 static struct timeval uname = {0,0};
296
make_uname(new_uname)297 void make_uname(new_uname)
298 struct timeval *new_uname;
299 {
300 /* generate a uname */
301 CRITICAL(uname_lock,
302 {
303 new_uname->tv_sec = uname.tv_sec;
304 new_uname->tv_usec = uname.tv_usec++;
305 if (uname.tv_usec >= 1000000)
306 {
307 uname.tv_sec++;
308 uname.tv_usec = 0;
309 }
310 });
311 }
312
313 /* uname initialization */
init_unames()314 long init_unames()
315 {
316 struct timeval new_uname;
317 long retval;
318
319 retval= gettimeofday(&new_uname,(struct timezone *)NULL);
320 if ( retval ) {
321 printf("init_unames: retval %ld\n", retval);
322 perror("init_names:");
323 return retval;
324 }
325
326 CRITICAL(uname_lock,
327 {
328 if (TIME_GTR(new_uname,uname))
329 uname = new_uname;
330 });
331
332 return 0;
333 }
334
335 /* module initialization */
336 /* Locks cannot be statically allocated in pthreads. */
init_utils()337 long init_utils()
338 {
339 CRITICAL(free_lists_init_lock,
340 {
341 if (!free_lists_inited)
342 {
343 init_free_lists();
344 free_lists_inited = rvm_true;
345 }
346 });
347
348 return init_unames();
349 }
350 /* time value arithmetic */
add_times(x,y)351 struct timeval add_times(x,y)
352 struct timeval *x;
353 struct timeval *y;
354 {
355 struct timeval tmp;
356
357 tmp.tv_sec = x->tv_sec + y->tv_sec;
358 tmp.tv_usec = x->tv_usec + y->tv_usec;
359 if (tmp.tv_usec >= 1000000)
360 {
361 tmp.tv_sec++;
362 tmp.tv_usec -= 1000000;
363 }
364 return tmp;
365 }
366
sub_times(x,y)367 struct timeval sub_times(x,y)
368 struct timeval *x;
369 struct timeval *y;
370 {
371 struct timeval tmp;
372
373 tmp = *x;
374 if (tmp.tv_usec < y->tv_usec)
375 {
376 tmp.tv_sec--;
377 tmp.tv_usec += 1000000;
378 }
379 tmp.tv_usec -= y->tv_usec;
380 tmp.tv_sec -= y->tv_sec;
381 return tmp;
382 }
383
384 /* round time to seconds */
round_time(x)385 long round_time(x)
386 struct timeval *x;
387 {
388 if (x->tv_usec >= 500000)
389 return x->tv_sec+1;
390
391 return x->tv_sec;
392 }
393 /* region descriptor allocator/finalizer */
make_region()394 region_t *make_region()
395 {
396 region_t *region;
397
398 region = (region_t *)alloc_list_entry(region_id);
399 if (region != NULL)
400 {
401 init_rw_lock(®ion->region_lock);
402 mutex_init(®ion->count_lock);
403 }
404 return region;
405 }
406
free_region(region)407 void free_region(region)
408 region_t *region;
409 {
410 assert(region->links.struct_id == region_id);
411 assert(LOCK_FREE(region->count_lock));
412
413 rw_lock_clear(®ion->region_lock);
414 mutex_clear(®ion->count_lock);
415 free_list_entry((list_entry_t *) region);
416 }
417 /* construct full path name for file names */
make_full_name(dev_str,dev_name,retval)418 char *make_full_name(dev_str,dev_name,retval)
419 char *dev_str; /* device name */
420 char *dev_name; /* device name buffer for descriptor */
421 rvm_return_t *retval; /* return code */
422 {
423 char wd_name[MAXPATHLEN+1]; /* current working directory */
424 long wd_len = 0; /* working dir string length */
425 long len; /* length of total device path */
426
427 *retval = RVM_SUCCESS;
428 len = strlen(dev_str) + 1; /* one extra for null terminator */
429
430 /* see if working directory must be added to device name */
431 if (*dev_str != '/')
432 {
433 if (getcwd(wd_name, sizeof(wd_name)) == 0)
434 assert(rvm_false);
435 wd_len = strlen(wd_name);
436 len += (wd_len+1); /* one extra for '/' */
437 }
438 if (len > (MAXPATHLEN+1))
439 {
440 *retval = RVM_ENAME_TOO_LONG;
441 return NULL;
442 }
443
444 /* allocate buffer, if necessary, and copy full path name */
445 if (dev_name == NULL)
446 if ((dev_name=malloc(len)) == NULL)
447 {
448 *retval = RVM_ENO_MEMORY;
449 return NULL;
450 }
451
452 *dev_name = 0;
453 if (wd_len != 0)
454 {
455 (void)strcpy(dev_name,wd_name);
456 dev_name[wd_len] = '/';
457 dev_name[wd_len+1] = 0;
458 }
459 (void)strcat(dev_name,dev_str);
460
461 return dev_name;
462 }
463 /* device descriptor initializer */
dev_init(dev,dev_str)464 rvm_return_t dev_init(dev,dev_str)
465 device_t *dev; /* device descriptor */
466 char *dev_str; /* device name */
467 {
468 rvm_return_t retval;
469
470 /* set device name */
471 if (dev_str != NULL)
472 {
473 dev->name = make_full_name(dev_str,NULL,&retval);
474 if (retval != RVM_SUCCESS) return retval;
475 dev->name_len = strlen(dev->name)+1;
476 }
477
478 dev->iov = NULL;
479 dev->iov_length = 0;
480 dev->raw_io = rvm_false;
481 dev->read_only = rvm_false;
482 dev->wrt_buf = NULL;
483 dev->buf_start = NULL;
484 dev->buf_end = NULL;
485 dev->ptr = NULL;
486 RVM_ZERO_OFFSET(dev->sync_offset);
487 dev->pad_buf = NULL;
488 dev->pad_buf_len = 0;
489
490 return RVM_SUCCESS;
491 }
492 /* segment descriptor allocator/finalizer */
make_seg(seg_dev_name,retval)493 seg_t *make_seg(seg_dev_name,retval)
494 char *seg_dev_name; /* segment device name */
495 rvm_return_t *retval; /* return code */
496 {
497 seg_t *seg;
498
499 /* initialize segment descriptor */
500 seg = (seg_t *)alloc_list_entry(seg_id);
501 if (seg != NULL)
502 {
503 /* initialize segment device */
504 if ((*retval=dev_init(&seg->dev,seg_dev_name)) != RVM_SUCCESS)
505 {
506 free(seg);
507 return NULL; /* no space for device name */
508 }
509
510 /* initialize the lists & locks*/
511 mutex_init(&seg->seg_lock);
512 mutex_init(&seg->dev_lock);
513 init_list_header(&seg->map_list,region_id);
514 init_list_header(&seg->unmap_list,region_id);
515 }
516
517 return seg;
518 }
519
free_seg(seg)520 void free_seg(seg)
521 seg_t *seg;
522 {
523 assert(seg->links.struct_id == seg_id);
524
525 /* all lists should be empty and locks free */
526 assert(LIST_EMPTY(seg->map_list));
527 assert(LIST_EMPTY(seg->unmap_list));
528 assert(LOCK_FREE(seg->seg_lock));
529 assert(LOCK_FREE(seg->dev_lock));
530
531 mutex_clear(&seg->seg_lock);
532 mutex_clear(&seg->dev_lock);
533 if (seg->dev.name != NULL)
534 {
535 free(seg->dev.name); /* free device name char array */
536 seg->dev.name = NULL;
537 }
538 free_list_entry(&seg->links);
539 }
540 /* segemnt dictionary finalizer */
free_seg_dict_vec(log)541 void free_seg_dict_vec(log)
542 log_t *log;
543 {
544 int i; /* loop counter */
545
546 if (log->seg_dict_vec != NULL)
547 {
548 /* free tree roots */
549 for (i=0; i < log->seg_dict_len; i++)
550 clear_tree_root(&log->seg_dict_vec[i].mod_tree);
551
552 free((char *)log->seg_dict_vec);
553 log->seg_dict_vec = NULL;
554 log->seg_dict_len = 0;
555 }
556 }
557 /* log descriptor finalizer */
free_log(log)558 void free_log(log)
559 log_t *log;
560 {
561 assert(log->links.struct_id == log_id);
562 assert(LIST_EMPTY(log->tid_list)); /* should not be any transactions
563 now */
564 assert(LIST_EMPTY(log->flush_list)); /* should not be any queued no_flush
565 transactions either */
566 assert(LIST_EMPTY(log->special_list)); /* no special log records should
567 be left */
568 assert(LOCK_FREE(log->dev_lock)); /* all locks should be free */
569 assert(LOCK_FREE(log->tid_list_lock));
570 assert(LOCK_FREE(log->flush_list_lock));
571 assert(LOCK_FREE(log->special_list_lock));
572 assert(RW_LOCK_FREE(log->flush_lock));
573 assert(LOCK_FREE(log->truncation_lock));
574 assert(LOCK_FREE(log->daemon.lock));
575 assert((log->daemon.thread != ZERO)
576 ? log->daemon.state == terminate : 1);
577
578 /* finalizer control structures */
579 mutex_clear(&log->dev_lock);
580 mutex_clear(&log->tid_list_lock);
581 mutex_clear(&log->flush_list_lock);
582 mutex_clear(&log->special_list_lock);
583 rw_lock_clear(&log->flush_lock);
584 mutex_clear(&log->truncation_lock);
585 mutex_clear(&log->daemon.lock);
586 condition_clear(&log->daemon.code);
587 condition_clear(&log->daemon.flush_flag);
588 condition_clear(&log->daemon.wake_up);
589
590 /* free malloc-ed buffers */
591 if (log->dev.name != NULL)
592 free(log->dev.name); /* kill name string */
593 if (log->dev.iov != NULL)
594 free((char *)log->dev.iov); /* kill io vector */
595 if (log->dev.wrt_buf != NULL) /* kill raw io gather write buffer */
596 page_free(log->dev.wrt_buf,log->dev.wrt_buf_len);
597 log->dev.wrt_buf_len = 0;
598 log->dev.name = NULL;
599 log->dev.iov = NULL;
600 free_log_buf(log); /* kill recovery buffers */
601
602 free_list_entry(&log->links); /* free descriptor */
603 }
604 /* log descriptor allocation */
make_log(log_dev_name,retval)605 log_t *make_log(log_dev_name,retval)
606 char *log_dev_name; /* device name */
607 rvm_return_t *retval; /* return code */
608 {
609 log_t *log;
610 log_buf_t *log_buf;
611
612 /* initialize log descriptor */
613 if ((log = (log_t *)alloc_list_entry(log_id)) != NULL)
614 {
615 /* init device and status */
616 if ((*retval=dev_init(&log->dev,log_dev_name)) != RVM_SUCCESS)
617 {
618 free(log);
619 return NULL; /* no space for device name */
620 }
621 /* first and foremost */
622 log->trunc_thread = (cthread_t) 0;
623
624 log->status.valid = rvm_false;
625 log->status.log_empty = rvm_false;
626 log->status.trunc_state = 0;
627 log->status.flush_state = 0;
628
629 /* init log flush structures */
630 log->trans_hdr.rec_hdr.struct_id = trans_hdr_id;
631 log->rec_end.rec_hdr.struct_id = rec_end_id;
632 log->log_wrap.rec_hdr.struct_id = log_wrap_id;
633 log->log_wrap.struct_id2 = log_wrap_id; /* for scan_wrap_reverse() */
634 log->log_wrap.rec_hdr.rec_length = sizeof(log_wrap_t);
635
636 /* init recovery buffer and dictionary */
637 log_buf = &log->log_buf;
638 log_buf->buf = NULL;
639 log_buf->length = 0;
640 RVM_ZERO_OFFSET(log_buf->buf_len);
641 log_buf->aux_buf = NULL;
642 log_buf->aux_length = 0;
643 log_buf->split_ok = rvm_false;
644 log->seg_dict_vec = NULL;
645 log->seg_dict_len = 0;
646 log->in_recovery = rvm_false;
647 mutex_init(&log->truncation_lock);
648 init_rw_lock(&log->flush_lock);
649 log_buf->prev_rec_num = 0;
650 ZERO_TIME(log_buf->prev_timestamp);
651 log_buf->prev_direction = rvm_false;
652
653 /* init lists and locks */
654 mutex_init(&log->dev_lock);
655 mutex_init(&log->tid_list_lock);
656 init_list_header(&log->tid_list,int_tid_id);
657 mutex_init(&log->flush_list_lock);
658 init_list_header(&log->flush_list,int_tid_id);
659 mutex_init(&log->special_list_lock);
660 init_list_header(&log->special_list,log_special_id);
661
662 /* init daemon control structure */
663 log->daemon.thread = ZERO;
664 mutex_init(&log->daemon.lock);
665 condition_init(&log->daemon.code);
666 condition_init(&log->daemon.flush_flag);
667 condition_init(&log->daemon.wake_up);
668 log->daemon.state = rvm_idle;
669 }
670
671 return log;
672 }
673 /* log special types allocation/deallocation */
make_log_special(special_id,length)674 log_special_t *make_log_special(special_id,length)
675 struct_id_t special_id; /* id of special type */
676 rvm_length_t length; /* length of type-specific allocation */
677 {
678 log_special_t *special; /* ptr to descriptor allocated */
679 char *buf=NULL; /* type-specific buffer */
680
681 if ((special=(log_special_t *)alloc_list_entry(log_special_id))
682 != NULL)
683 {
684 special->rec_hdr.struct_id = special_id; /* set "real" type */
685
686 /* buffer allocation */
687 if ((length=ROUND_TO_LENGTH(length)) != 0)
688 if ((buf = calloc(1, (unsigned)length)) == NULL)
689 {
690 free_list_entry((list_entry_t *)special);
691 return NULL;
692 }
693 special->rec_hdr.rec_length = LOG_SPECIAL_SIZE + length;
694
695 /* type specific initialization */
696 switch (special_id)
697 {
698 case log_seg_id:
699 special->special.log_seg.name=buf;
700 break;
701 default: assert(rvm_false); /* should never happen */
702 }
703 }
704
705 return special;
706 }
free_log_special(special)707 void free_log_special(special)
708 log_special_t *special; /* ptr to descriptor allocated */
709 {
710 assert(special->links.struct_id == log_special_id);
711
712 /* type specific finalization */
713 switch (special->rec_hdr.struct_id)
714 {
715 case log_seg_id:
716 if (special->special.log_seg.name != NULL)
717 {
718 free(special->special.log_seg.name);
719 special->special.log_seg.name = NULL;
720 }
721 break;
722 default: assert(rvm_false); /* should not happen */
723 }
724
725 free_list_entry((list_entry_t *)special);
726
727 }
728 /* range descriptor allocator/finalizer */
make_range()729 range_t *make_range()
730 {
731 register range_t *range;
732
733 if ((range = (range_t *)alloc_list_entry(range_id)) != NULL)
734 {
735 range->links.node.lss = NULL;
736 range->links.node.gtr = NULL;
737 range->links.node.bf = 0;
738 range->nvaddr = NULL;
739 range->data = NULL;
740 range->data_len = 0;
741 range->nv.rec_hdr.struct_id = nv_range_id;
742 range->nv.is_split = rvm_false;
743 }
744
745 return range;
746 }
747
free_range(range)748 void free_range(range)
749 register range_t *range;
750 {
751 assert(range->links.node.struct_id == range_id);
752
753 if (range->data != NULL)
754 {
755 free(range->data);
756 range->data = NULL;
757 range->nvaddr = NULL;
758 range->data_len = 0;
759 }
760
761 range->links.entry.list.name = NULL; /* not really on any list */
762 range->links.entry.is_hdr = rvm_false;
763 free_list_entry(&range->links.entry);
764 }
765 /* internal transaction descriptor allocator/finalizer */
766
make_tid(mode)767 int_tid_t *make_tid(mode)
768 rvm_mode_t mode; /* transaction begin mode */
769 {
770 register int_tid_t *tid;
771
772 tid = (int_tid_t *)alloc_list_entry(int_tid_id);
773 if (tid != NULL)
774 {
775 make_uname(&tid->uname);
776 init_rw_lock(&tid->tid_lock);
777 init_tree_root(&tid->range_tree);
778 tid->x_ranges = NULL;
779 tid->x_ranges_alloc = 0;
780 tid->x_ranges_len = 0;
781 tid->n_coalesced = 0;
782 tid->range_elim = 0;
783 tid->trans_elim = 0;
784 RVM_ZERO_OFFSET(tid->range_overlap);
785 RVM_ZERO_OFFSET(tid->trans_overlap);
786 ZERO_TIME(tid->commit_stamp);
787 tid->flags = rvm_optimizations & RVM_ALL_OPTIMIZATIONS;
788 if (mode == restore) tid->flags |= RESTORE_FLAG;
789 tid->split_range.nv.rec_hdr.struct_id = nv_range_id;
790 tid->back_link = sizeof(trans_hdr_t);
791 }
792
793 return tid;
794 }
795
free_tid(tid)796 void free_tid(tid)
797 register int_tid_t *tid;
798 {
799 range_t *range;
800
801 assert(tid->links.struct_id == int_tid_id);
802 rw_lock_clear(&tid->tid_lock);
803
804 /* free range list */
805 UNLINK_NODES_OF(tid->range_tree,range_t,range)
806 free_range((range_t *)range);
807 clear_tree_root(&tid->range_tree);
808
809 /* free search vector */
810 if (tid->x_ranges != NULL)
811 {
812 free(tid->x_ranges);
813 tid->x_ranges = NULL;
814 }
815
816 /* free tid */
817 free_list_entry(&tid->links);
818 }
819 /* mem_region nodes for mapping */
make_mem_region()820 mem_region_t *make_mem_region()
821 {
822 register mem_region_t *node;
823
824 node = (mem_region_t *)alloc_list_entry(mem_region_id);
825 if (node != NULL)
826 {
827 node->region = NULL;
828 }
829
830 return node;
831 }
832
free_mem_region(node)833 void free_mem_region(node)
834 register mem_region_t *node;
835 {
836 assert(node->links.node.struct_id == mem_region_id);
837
838 /* free node */
839 node->links.entry.list.name = NULL; /* not really on any list */
840 node->links.entry.is_hdr = rvm_false;
841 free_list_entry(&node->links.entry);
842 }
843 /* dev_region nodes for recovery */
make_dev_region()844 dev_region_t *make_dev_region()
845 {
846 register dev_region_t *node;
847
848 node = (dev_region_t *)alloc_list_entry(dev_region_id);
849 if (node == NULL) return NULL;
850
851 node->nv_buf = NULL;
852 node->nv_ptr = NULL;
853 RVM_ZERO_OFFSET(node->log_offset);
854
855 return node;
856 }
857
free_dev_region(node)858 void free_dev_region(node)
859 register dev_region_t *node;
860 {
861 assert(node->links.node.struct_id == dev_region_id);
862
863 /* free node */
864 node->links.entry.list.name = NULL; /* not really on any list */
865 node->links.entry.is_hdr = rvm_false;
866
867 if (node->nv_buf != NULL)
868 {
869 assert(node->nv_buf->struct_id == nv_buf_id);
870 if ((--(node->nv_buf->ref_cnt)) == 0)
871 {
872 free(node->nv_buf);
873 node->nv_buf = NULL;
874 node->nv_ptr = NULL;
875 }
876 }
877 free_list_entry(&node->links.entry);
878 }
879 /* RVM exported structures support */
880
free_export(cell,struct_id)881 static void free_export(cell,struct_id)
882 list_entry_t *cell;
883 struct_id_t struct_id;
884 {
885 cell->struct_id = struct_id;
886 cell->list.name = NULL;
887 cell->preventry = NULL;
888 cell->nextentry = NULL;
889 cell->is_hdr = rvm_false;
890 free_list_entry(cell);
891 }
892
893
894 /* rvm_region_t functions */
rvm_malloc_region()895 rvm_region_t *rvm_malloc_region()
896 {
897 rvm_region_t *new_rvm_region;
898
899 if (!free_lists_inited) (void)init_utils();
900 new_rvm_region = (rvm_region_t *)alloc_list_entry(region_rvm_id);
901 if (new_rvm_region != NULL)
902 {
903 rvm_init_region(new_rvm_region);
904 new_rvm_region->from_heap = rvm_true;
905 }
906 return new_rvm_region;
907 }
908
rvm_free_region(rvm_region)909 void rvm_free_region(rvm_region)
910 rvm_region_t *rvm_region;
911 {
912 if ((!bad_region(rvm_region))&&(free_lists_inited)&&
913 (rvm_region->from_heap))
914 free_export((list_entry_t *)rvm_region,region_rvm_id);
915 }
rvm_init_region(rvm_region)916 void rvm_init_region(rvm_region)
917 rvm_region_t *rvm_region;
918 {
919 BZERO((char *) rvm_region,sizeof(rvm_region_t));
920 rvm_region->struct_id = rvm_region_id;
921 }
922
rvm_copy_region(rvm_region)923 rvm_region_t *rvm_copy_region(rvm_region)
924 rvm_region_t *rvm_region;
925 {
926 rvm_region_t *new_rvm_region;
927
928 if (bad_region(rvm_region)) return NULL;
929 if (!free_lists_inited) (void)init_utils();
930
931 new_rvm_region = (rvm_region_t *)alloc_list_entry(region_rvm_id);
932 if (new_rvm_region != NULL)
933 {
934 (void)BCOPY((char *)rvm_region,(char *)new_rvm_region,
935 sizeof(rvm_region_t));
936 new_rvm_region->from_heap = rvm_true;
937 }
938 return new_rvm_region;
939 }
940 /* rvm_statistics_t functions */
rvm_malloc_statistics()941 rvm_statistics_t *rvm_malloc_statistics()
942 {
943 rvm_statistics_t *new_rvm_statistics;
944
945 new_rvm_statistics = (rvm_statistics_t *)
946 alloc_list_entry(statistics_rvm_id);
947 if (new_rvm_statistics != NULL)
948 {
949 rvm_init_statistics(new_rvm_statistics);
950 new_rvm_statistics->from_heap = rvm_true;
951 }
952 return new_rvm_statistics;
953 }
954
rvm_free_statistics(rvm_statistics)955 void rvm_free_statistics(rvm_statistics)
956 rvm_statistics_t *rvm_statistics;
957 {
958 if ((!bad_statistics(rvm_statistics)) && (free_lists_inited)
959 && (rvm_statistics->from_heap))
960 free_export((list_entry_t *)rvm_statistics,statistics_rvm_id);
961 }
rvm_init_statistics(rvm_statistics)962 void rvm_init_statistics(rvm_statistics)
963 rvm_statistics_t *rvm_statistics;
964 {
965 if (rvm_statistics != NULL)
966 {
967 BZERO((char *)rvm_statistics,sizeof(rvm_statistics_t));
968 rvm_statistics->struct_id = rvm_statistics_id;
969 }
970 }
971
rvm_copy_statistics(rvm_statistics)972 rvm_statistics_t *rvm_copy_statistics(rvm_statistics)
973 rvm_statistics_t *rvm_statistics;
974 {
975 rvm_statistics_t *new_rvm_statistics;
976
977 if (bad_statistics(rvm_statistics)) return NULL;
978 if (!free_lists_inited) (void)init_utils();
979
980 new_rvm_statistics =
981 (rvm_statistics_t *)alloc_list_entry(statistics_rvm_id);
982 if (new_rvm_statistics != NULL)
983 {
984 (void) BCOPY((char *)rvm_statistics,(char *)new_rvm_statistics,
985 sizeof(rvm_statistics_t));
986 new_rvm_statistics->from_heap = rvm_true;
987 }
988 return new_rvm_statistics;
989 }
990 /* rvm_options_t functions */
991
rvm_malloc_options()992 rvm_options_t *rvm_malloc_options()
993 {
994 rvm_options_t *new_rvm_options;
995
996 if (!free_lists_inited) (void)init_utils();
997 new_rvm_options = (rvm_options_t *)
998 alloc_list_entry(options_rvm_id);
999 if (new_rvm_options != NULL)
1000 {
1001 rvm_init_options(new_rvm_options);
1002 new_rvm_options->from_heap = rvm_true;
1003 }
1004 return new_rvm_options;
1005 }
1006
rvm_free_options(rvm_options)1007 void rvm_free_options(rvm_options)
1008 rvm_options_t *rvm_options;
1009 {
1010 if (!bad_options(rvm_options, rvm_false) && free_lists_inited &&
1011 rvm_options->from_heap)
1012 {
1013 /* release tid_array */
1014 if (rvm_options->tid_array != NULL)
1015 {
1016 free((char *)rvm_options->tid_array);
1017 rvm_options->tid_array = (rvm_tid_t *)NULL;
1018 rvm_options->n_uncommit = 0;
1019 }
1020
1021 /* free options record */
1022 free_export((list_entry_t *)rvm_options,options_rvm_id);
1023 }
1024 }
rvm_init_options(rvm_options)1025 void rvm_init_options(rvm_options)
1026 rvm_options_t *rvm_options;
1027 {
1028 if (rvm_options != NULL)
1029 {
1030 BZERO((char *)rvm_options,sizeof(rvm_options_t));
1031 rvm_options->struct_id = rvm_options_id;
1032 rvm_options->truncate = TRUNCATE;
1033 rvm_options->recovery_buf_len = RECOVERY_BUF_LEN;
1034 rvm_options->flush_buf_len = FLUSH_BUF_LEN;
1035 rvm_options->max_read_len = MAX_READ_LEN;
1036 rvm_options->create_log_file = rvm_false;
1037 RVM_ZERO_OFFSET(rvm_options->create_log_size);
1038 rvm_options->create_log_mode = 0600;
1039 }
1040 }
1041
rvm_copy_options(rvm_options)1042 rvm_options_t *rvm_copy_options(rvm_options)
1043 rvm_options_t *rvm_options;
1044 {
1045 rvm_options_t *new_rvm_options;
1046
1047 if (bad_options(rvm_options, rvm_true)) return NULL;
1048 if (!free_lists_inited) (void)init_utils();
1049
1050 new_rvm_options = (rvm_options_t *)
1051 alloc_list_entry(options_rvm_id);
1052 if (new_rvm_options != NULL)
1053 {
1054 (void) BCOPY((char *)rvm_options,(char *)new_rvm_options,
1055 sizeof(rvm_options_t));
1056 new_rvm_options->from_heap = rvm_true;
1057 }
1058 return new_rvm_options;
1059 }
1060 /* rvm_tid_t functions */
1061
rvm_malloc_tid()1062 rvm_tid_t *rvm_malloc_tid()
1063 {
1064 rvm_tid_t *new_rvm_tid;
1065
1066 if (!free_lists_inited) (void)init_utils();
1067 new_rvm_tid = (rvm_tid_t *)alloc_list_entry(tid_rvm_id);
1068 if (new_rvm_tid != NULL)
1069 {
1070 rvm_init_tid(new_rvm_tid);
1071 new_rvm_tid->from_heap = rvm_true;
1072 }
1073 return new_rvm_tid;
1074 }
1075
rvm_free_tid(rvm_tid)1076 void rvm_free_tid(rvm_tid)
1077 rvm_tid_t *rvm_tid;
1078 {
1079 if ((!bad_tid(rvm_tid))&&(free_lists_inited)&&
1080 (rvm_tid->from_heap))
1081 free_export((list_entry_t *)rvm_tid,tid_rvm_id);
1082 }
1083
rvm_init_tid(rvm_tid_t * rvm_tid)1084 void rvm_init_tid(rvm_tid_t *rvm_tid)
1085 {
1086 if (rvm_tid != NULL) {
1087 BZERO((char *)rvm_tid,sizeof(rvm_tid_t));
1088 rvm_tid->struct_id = rvm_tid_id;
1089 }
1090 }
1091
rvm_copy_tid(rvm_tid)1092 rvm_tid_t *rvm_copy_tid(rvm_tid)
1093 rvm_tid_t *rvm_tid;
1094 {
1095 rvm_tid_t *new_rvm_tid;
1096
1097 if (bad_tid(rvm_tid)) return NULL;
1098 if (!free_lists_inited) (void)init_utils();
1099
1100 new_rvm_tid = (rvm_tid_t *)alloc_list_entry(tid_rvm_id);
1101 if (new_rvm_tid != NULL)
1102 {
1103 (void) BCOPY((char *)rvm_tid,(char *)new_rvm_tid,
1104 sizeof(rvm_tid_t));
1105 new_rvm_tid->from_heap = rvm_true;
1106 }
1107 return new_rvm_tid;
1108 }
1109 /* RVM User enumeration type print name support */
1110 static char *return_codes[(long)rvm_last_code-(long)rvm_first_code-1] =
1111 {
1112 "RVM_EINIT","RVM_EINTERNAL","RVM_EIO","RVM_EPLACEHOLDER","RVM_ELOG",
1113 "RVM_ELOG_VERSION_SKEW","RVM_EMODE","RVM_ENAME_TOO_LONG",
1114 "RVM_ENO_MEMORY","RVM_ENOT_MAPPED","RVM_EOFFSET",
1115 "RVM_EOPTIONS","RVM_EOVERLAP","RVM_EPAGER","RVM_ERANGE",
1116 "RVM_EREGION","RVM_EREGION_DEF","RVM_ESRC","RVM_ESTATISTICS",
1117 "RVM_ESTAT_VERSION_SKEW","RVM_ETERMINATED","RVM_ETHREADS",
1118 "RVM_ETID","RVM_ETOO_BIG","RVM_EUNCOMMIT",
1119 "RVM_EVERSION_SKEW","RVM_EVM_OVERLAP"
1120 };
1121
1122 static char *rvm_modes[(long)rvm_last_mode-(long)rvm_first_mode-1] =
1123 {
1124 "restore","no_restore","flush","no_flush"
1125 };
1126
1127 static char *rvm_types[(long)rvm_last_struct_id-(long)rvm_first_struct_id-1] =
1128 {
1129 "rvm_region_t","rvm_options_t","rvm_tid_t","rvm_statistics_id"
1130 };
1131 /* RVM enumeration type print name routines */
rvm_return(code)1132 char *rvm_return(code)
1133 rvm_return_t code;
1134 {
1135 if (code == RVM_SUCCESS) return "RVM_SUCCESS";
1136
1137 if (((long)code > (long)rvm_first_code) &&
1138 ((long)code < (long)rvm_last_code))
1139 return return_codes[(long)code-(long)rvm_first_code-1];
1140 else
1141 return "Invalid RVM return code";
1142 }
rvm_mode(mode)1143 char *rvm_mode(mode)
1144 rvm_mode_t mode;
1145 {
1146 if (((long)mode > (long)rvm_first_mode) &&
1147 ((long)mode < (long)rvm_last_mode))
1148 return rvm_modes[(long)mode-(long)rvm_first_mode-1];
1149 else
1150 return "Invalid RVM transaction mode";
1151 }
rvm_type(id)1152 char *rvm_type(id)
1153 rvm_struct_id_t id;
1154 {
1155 if (((long)id > (long)rvm_first_struct_id) &&
1156 ((long)id < (long)rvm_last_struct_id))
1157 return rvm_types[(long)id-(long)rvm_first_struct_id-1];
1158 else
1159 return "Invalid RVM structure type";
1160 }
1161 /* Byte-aligned checksum and move functions */
1162
1163 /* zero-pad unused bytes of word */
zero_pad_word(word,addr,leading)1164 static rvm_length_t zero_pad_word(word,addr,leading)
1165 rvm_length_t word; /* value to be zero-padded */
1166 char *addr; /* address of 1st/last byte */
1167 rvm_bool_t leading; /* true if leading bytes are zeroed */
1168 {
1169 char *word_array = (char *)&word; /* byte access of
1170 word value */
1171 int skew = BYTE_SKEW(addr);
1172 int i;
1173
1174 if (leading) /* zero pad leading bytes */
1175 {
1176 for (i=sizeof(rvm_length_t)-1; i>0; i--)
1177 if (i <= skew) word_array[i-1] = 0;
1178 }
1179 else /* zero pad trailing bytes */
1180 {
1181 for (i=0; i<(sizeof(rvm_length_t)-1); i++)
1182 if (i >= skew) word_array[i+1] = 0;
1183 }
1184
1185 return word;
1186 }
1187 /* checksum function: forms checksum of arbitrarily aligned range
1188 by copying preceeding, trailing bytes to make length 0 mod length size */
chk_sum(nvaddr,len)1189 rvm_length_t chk_sum(nvaddr,len)
1190 char *nvaddr; /* address of 1st byte */
1191 rvm_length_t len; /* byte count */
1192 {
1193 rvm_length_t *base; /* 0 mod sizeof(rvm_length_t) addr */
1194 rvm_length_t length; /* number of words to sum */
1195 rvm_length_t chk_sum; /* check sum temp */
1196 rvm_length_t i;
1197
1198 if (len == 0) return 0;
1199
1200 /* get zero-byte aligned base address & length of region */
1201 base = (rvm_length_t *)CHOP_TO_LENGTH(nvaddr);
1202 length = (ALIGNED_LEN(nvaddr,len)/sizeof(rvm_length_t)) - 1;
1203
1204 /* process boundary words */
1205 chk_sum = zero_pad_word(*base,nvaddr,rvm_true);
1206 if (length >= 2)
1207 chk_sum += zero_pad_word(base[length],&nvaddr[len-1],rvm_false);
1208 if (length <= 1) return chk_sum;
1209
1210 /* form check sum of remaining full words */
1211 for (i=1; i < length; i++)
1212 chk_sum += base[i];
1213
1214 return chk_sum;
1215 }
1216 /* copy arbitrarily aligned range, maintaining 1st src byte alignment */
src_aligned_bcopy(src,dest,len)1217 void src_aligned_bcopy(src,dest,len)
1218 char *src; /* source address */
1219 char *dest; /* destination address */
1220 rvm_length_t len; /* length of range */
1221 {
1222
1223 if (len != 0)
1224 (void)BCOPY(src,
1225 RVM_ADD_LENGTH_TO_ADDR(dest,BYTE_SKEW(src)),
1226 len);
1227
1228 }
1229
1230 /* copy arbitrarily aligned range, maintaining 1st dest byte alignment */
dest_aligned_bcopy(src,dest,len)1231 void dest_aligned_bcopy(src,dest,len)
1232 char *src; /* source address */
1233 char *dest; /* destination address */
1234 rvm_length_t len; /* length of range */
1235 {
1236
1237 if (len != 0)
1238 (void)BCOPY(RVM_ADD_LENGTH_TO_ADDR(src,BYTE_SKEW(dest)),
1239 dest,len);
1240
1241 }
1242 /* rw_lock functions */
1243
1244 /* rw_lock initializer */
init_rw_lock(rwl)1245 void init_rw_lock(rwl)
1246 rw_lock_t *rwl;
1247 {
1248
1249 mutex_init(&rwl->mutex);
1250 init_list_header(&rwl->queue,rw_qentry_id);
1251 rwl->read_cnt = 0;
1252 rwl->write_cnt = 0;
1253 rwl->lock_mode = f;
1254 }
1255
1256 /* rw_lock finalizer */
rw_lock_clear(rw_lock_t * rwl)1257 static void rw_lock_clear(rw_lock_t *rwl)
1258 {
1259 assert(LOCK_FREE(rwl->mutex));
1260 assert(LIST_EMPTY(rwl->queue));
1261 assert(rwl->read_cnt == 0);
1262 assert(rwl->write_cnt == 0);
1263 assert(rwl->lock_mode == f);
1264
1265 mutex_clear(&rwl->mutex);
1266 }
rw_lock(rwl,mode)1267 void rw_lock(rwl,mode)
1268 rw_lock_t *rwl; /* ptr to rw_lock structure */
1269 rw_lock_mode_t mode; /* r or w */
1270 {
1271 #ifdef RVM_USELWP
1272 if (mode == r) ObtainReadLock(&rwl->mutex);
1273 else ObtainWriteLock(&rwl->mutex);
1274 #else
1275 rw_qentry_t q; /* queue entry */
1276
1277 CRITICAL(rwl->mutex, /* begin rw_lock mutex crit sec */
1278 {
1279 assert((mode == r) || (mode == w));
1280 assert(rwl->read_cnt >= 0);
1281 assert((rwl->write_cnt >= 0) && (rwl->write_cnt <= 1));
1282 assert((rwl->write_cnt > 0) ? (rwl->read_cnt == 0) : 1);
1283 assert((rwl->read_cnt > 0) ? (rwl->write_cnt == 0) : 1);
1284
1285 /* see if must block */
1286 if (((mode == w) && ((rwl->read_cnt+rwl->write_cnt) != 0))
1287 || ((mode == r) && (rwl->write_cnt != 0))
1288 || (LIST_NOT_EMPTY(rwl->queue))) /* this term prevents starvation
1289 of writers by readers */
1290 {
1291 /* must block: initialize queue entry & put on lock queue */
1292 q.links.struct_id = rw_qentry_id;
1293 q.links.is_hdr = rvm_false;
1294 q.links.list.name = NULL;
1295 condition_init(&q.wait);
1296 q.mode = mode;
1297 (void)move_list_entry(NULL,&rwl->queue,(list_entry_t *)&q);
1298
1299 /* wait to be signaled when access ready */
1300 condition_wait(&q.wait,&rwl->mutex);
1301 assert(rwl->lock_mode == mode);
1302 assert((mode == w) ?
1303 ((rwl->write_cnt==1) && (rwl->read_cnt==0)) : 1);
1304 assert((mode == r) ?
1305 ((rwl->write_cnt==0) && (rwl->read_cnt>=1)) : 1);
1306 }
1307 else
1308 { /* immediate access: set the lock */
1309 assert((rwl->lock_mode == r) || (rwl->lock_mode == f));
1310 if (mode == r) rwl->read_cnt++;
1311 else rwl->write_cnt++;
1312 rwl->lock_mode = mode;
1313 }
1314 }); /* end rw_lock mutex crit sec */
1315 #endif
1316 }
rw_unlock(rwl,mode)1317 void rw_unlock(rwl,mode)
1318 rw_lock_t *rwl; /* ptr to rw_lock structure */
1319 rw_lock_mode_t mode; /* r or w (for consistency chk only) */
1320 {
1321 #ifdef RVM_USELWP
1322 if (mode == r) ReleaseReadLock(&rwl->mutex);
1323 else ReleaseWriteLock(&rwl->mutex);
1324 #else
1325 rw_qentry_t *q,*old_q; /* thread queue elements */
1326
1327 CRITICAL(rwl->mutex, /* begin rw_lock mutex crit sec */
1328 {
1329 assert((mode == r) || (mode == w));
1330 assert(rwl->lock_mode == mode);
1331 assert(rwl->read_cnt >= 0);
1332 assert((rwl->write_cnt >= 0) && (rwl->write_cnt <= 1));
1333 assert((rwl->write_cnt > 0) ? (rwl->read_cnt == 0) : 1);
1334 assert((rwl->read_cnt > 0) ? (rwl->write_cnt == 0) : 1);
1335
1336 /* update lock counts */
1337 if (rwl->lock_mode == r)
1338 rwl->read_cnt--;
1339 else rwl->write_cnt--;
1340
1341 /* clear lock mode if lock free */
1342 if ((rwl->write_cnt == 0) && (rwl->read_cnt == 0))
1343 rwl->lock_mode = f;
1344
1345 /* see if any threads should be signaled */
1346 if (LIST_NOT_EMPTY(rwl->queue))
1347 {
1348 /* wake up single writer iff current readers done */
1349 q = (rw_qentry_t *)rwl->queue.nextentry;
1350 if (q->mode == w)
1351 {
1352 if (rwl->lock_mode == f)
1353 { /* wake up writer */
1354 q = (rw_qentry_t *)
1355 move_list_entry(&rwl->queue,NULL,NULL);
1356 rwl->write_cnt++;
1357 rwl->lock_mode = w;
1358 condition_signal(&q->wait);
1359 }
1360 else
1361 assert((rwl->lock_mode==r) && (rwl->write_cnt==0));
1362 }
1363 else
1364 do /* wake up all readers before next writer */
1365 {
1366 old_q = q; /* save entry ptr */
1367 q = (rw_qentry_t *)q->links.nextentry;
1368
1369 old_q = (rw_qentry_t *)
1370 move_list_entry(&rwl->queue,NULL,NULL);
1371 rwl->read_cnt++;
1372 assert(rwl->lock_mode != w);
1373 rwl->lock_mode = r;
1374 condition_signal(&old_q->wait);
1375 }
1376 while (!(q->links.is_hdr || (q->mode == w)));
1377 }
1378 }); /* end rw_lock mutex crit sec */
1379 #endif
1380 }
1381 /* binary tree functions
1382 all functions leave locking to caller
1383 lookup requires a comparator function with signature:
1384 int cmp(target,test)
1385 rvm_offset_t *target; node to locate
1386 rvm_offset_t *test; node to test against
1387
1388 returns: 1 target > test
1389 0 target = test
1390 -1 target < test
1391 */
1392 /* traversal vector initializer */
chk_traverse(tree)1393 static void chk_traverse(tree)
1394 tree_root_t *tree;
1395 {
1396 if (tree->traverse_len <= (tree->max_depth+1))
1397 {
1398 tree->traverse_len += TRAVERSE_LEN_INCR;
1399 if (tree->traverse != NULL)
1400 free((char *)tree->traverse);
1401 tree->traverse=(tree_pos_t *)
1402 malloc(tree->traverse_len*sizeof(tree_pos_t));
1403 if (tree->traverse == NULL)
1404 assert(rvm_false);
1405 }
1406 }
1407
1408 #define SET_TRAVERSE(tr,pt,st) \
1409 (tr)->traverse[++(tr)->level].ptr = (tree_node_t *)(pt); \
1410 (tr)->traverse[(tr)->level].state = (st)
1411
1412 /* tree root initialization */
init_tree_root(root)1413 void init_tree_root(root)
1414 tree_root_t *root;
1415 {
1416 root->struct_id = tree_root_id;
1417 root->root = NULL;
1418 root->traverse = NULL;
1419 root->traverse_len = 0;
1420 root->n_nodes = 0;
1421 root->max_depth = 0;
1422 root->unlink = rvm_false;
1423 }
1424
1425 /* tree root finalizer */
clear_tree_root(tree_root_t * root)1426 static void clear_tree_root(tree_root_t *root)
1427 {
1428 assert(root->struct_id == tree_root_id);
1429 if (root->traverse != NULL)
1430 {
1431 free(root->traverse);
1432 root->traverse = NULL;
1433 root->traverse_len = 0;
1434 }
1435 }
1436
1437 #ifdef UNUSED_FUNCTIONS
1438 /* balance checker */
get_depth(node,n_nodes)1439 static int get_depth(node,n_nodes)
1440 tree_node_t *node;
1441 long *n_nodes;
1442 {
1443 int lss_depth = 1; /* init to 1 for this node */
1444 int gtr_depth = 1;
1445
1446 if (node == NULL) return 0;
1447 assert((node->bf >= -1) && (node->bf <= 1));
1448
1449 if (n_nodes != NULL) (*n_nodes)++;
1450 lss_depth += get_depth(node->lss,n_nodes);
1451 gtr_depth += get_depth(node->gtr,n_nodes);
1452
1453 assert(node->bf == (gtr_depth - lss_depth)); /* check balance factor */
1454 assert((node->bf >= -1) && (node->bf <= 1));
1455
1456 if (gtr_depth > lss_depth) /* return depth of deeper side */
1457 return gtr_depth;
1458 else
1459 return lss_depth;
1460 }
1461
1462 /* Guaranteed to return 0, for now */
chk_balance(tree)1463 static int chk_balance(tree)
1464 tree_root_t *tree; /* ptr to root of tree */
1465 {
1466 long n_nodes = 0;
1467 get_depth(tree->root,&n_nodes);
1468
1469 assert(n_nodes == tree->n_nodes);
1470 return 0;
1471 }
1472 #endif
1473
1474 /* binary tree lookup -- returns ptr to node found (or NULL) */
tree_lookup(tree,node,cmp)1475 tree_node_t *tree_lookup(tree,node,cmp)
1476 tree_root_t *tree; /* root of tree */
1477 tree_node_t *node; /* node w/ range to lookup */
1478 cmp_func_t *cmp; /* ptr to comparator function */
1479 {
1480 tree_node_t *cur; /* current search node */
1481 tree_node_t *par = NULL; /* parent of cur */
1482
1483 assert(tree->struct_id == tree_root_id);
1484 cur = tree->root;
1485 while (cur != NULL) /* search */
1486 {
1487 assert(cur != par); /* loop detector */
1488 par = cur;
1489 switch ((*cmp)(node,cur))
1490 {
1491 case -1: /* lss */
1492 cur = cur->lss;
1493 break;
1494 case 0: /* match */
1495 return cur;
1496 case 1: /* gtr */
1497 cur = cur->gtr;
1498 break;
1499 default: assert(rvm_false);
1500 }
1501 }
1502
1503 return NULL; /* not found */
1504 }
1505 /* insertion rotation function */
insert_rotate(tree,bal_pnt,bal_pnt_par,sub_root,new_bf)1506 static void insert_rotate(tree,bal_pnt,bal_pnt_par,sub_root,new_bf)
1507 tree_root_t *tree; /* ptr to root of tree */
1508 tree_node_t *bal_pnt; /* balance point */
1509 tree_node_t *bal_pnt_par; /* parent of bal_pnt */
1510 tree_node_t *sub_root; /* root of unbalanced sub-tree */
1511 long new_bf; /* new balance factor */
1512 {
1513 tree_node_t *new_bal_pnt = sub_root; /* new balance node */
1514
1515 assert(tree->struct_id == tree_root_id);
1516 if (new_bf == 1)
1517 {
1518 /* right heavy */
1519 if (sub_root->bf == 1)
1520 {
1521 /* rotate RR */
1522 bal_pnt->gtr = sub_root->lss;
1523 sub_root->lss = bal_pnt;
1524 bal_pnt->bf = sub_root->bf = 0;
1525 }
1526 else
1527 {
1528 /* RL rotations */
1529 new_bal_pnt = sub_root->lss;
1530 sub_root->lss = new_bal_pnt->gtr;
1531 bal_pnt->gtr = new_bal_pnt->lss;
1532 new_bal_pnt->gtr = sub_root;
1533 new_bal_pnt->lss = bal_pnt;
1534
1535 /* adjust balance factors */
1536 switch (new_bal_pnt->bf)
1537 {
1538 case 0: bal_pnt->bf = sub_root->bf = 0;
1539 break;
1540 case 1: bal_pnt->bf = -1; sub_root->bf = 0;
1541 break;
1542 case -1: bal_pnt->bf = 0; sub_root->bf = 1;
1543 break;
1544 default: assert(rvm_false);
1545 }
1546 new_bal_pnt->bf = 0;
1547 }
1548 }
1549 else
1550 {
1551 /* left heavy */
1552 if (sub_root->bf == -1)
1553 {
1554 /* rotate LL */
1555 bal_pnt->lss = sub_root->gtr;
1556 sub_root->gtr = bal_pnt;
1557 bal_pnt->bf = sub_root->bf = 0;
1558 }
1559 else
1560 {
1561 /* LR rotations */
1562 new_bal_pnt = sub_root->gtr;
1563 sub_root->gtr = new_bal_pnt->lss;
1564 bal_pnt->lss = new_bal_pnt->gtr;
1565 new_bal_pnt->lss = sub_root;
1566 new_bal_pnt->gtr = bal_pnt;
1567
1568 /* adjust balance factors */
1569 switch (new_bal_pnt->bf)
1570 {
1571 case 0: bal_pnt->bf = sub_root->bf = 0;
1572 break;
1573 case 1: bal_pnt->bf = 0; sub_root->bf = -1;
1574 break;
1575 case -1: bal_pnt->bf = 1; sub_root->bf = 0;
1576 break;
1577 default: assert(rvm_false);
1578 }
1579 new_bal_pnt->bf = 0;
1580 }
1581 }
1582
1583 /* complete rotation by re-inserting balanced sub-tree */
1584 if (bal_pnt_par == NULL)
1585 tree->root = new_bal_pnt;
1586 else
1587 if (bal_pnt == bal_pnt_par->gtr)
1588 bal_pnt_par->gtr = new_bal_pnt;
1589 else
1590 if (bal_pnt == bal_pnt_par->lss)
1591 bal_pnt_par->lss = new_bal_pnt;
1592 }
1593 /* binary tree insertion - traverse vector left suitable for
1594 successor iterator */
tree_insert(tree,node,cmp)1595 rvm_bool_t tree_insert(tree,node,cmp)
1596 tree_root_t *tree; /* ptr to root of tree */
1597 tree_node_t *node; /* node to insert */
1598 cmp_func_t *cmp; /* comparator */
1599 {
1600 tree_node_t *cur; /* current search node */
1601 tree_node_t *par = NULL; /* parent of cur */
1602 tree_node_t *sub_root; /* root of unbalanced sub-tree */
1603 tree_node_t *last_unbal; /* last seen unbalanced node */
1604 tree_node_t *last_unbal_par = NULL; /* parent of last unbalanced node */
1605 int val=0; /* last comparison value */
1606 long new_bf; /* new balance factor */
1607
1608 assert(tree->struct_id == tree_root_id);
1609 chk_traverse(tree);
1610 node->gtr = node->lss = NULL;
1611 node->bf = 0;
1612 if (tree->root == NULL)
1613 {
1614 tree->root = node; /* insert node into empty tree */
1615 tree->n_nodes = tree->max_depth = 1;
1616 return rvm_true;
1617 }
1618
1619 /* search for insertion point */
1620 tree->level = -1;
1621 /* tree->root cannot be null */
1622 cur = last_unbal = tree->root;
1623 assert(cur != NULL);
1624 while (cur != NULL)
1625 {
1626 /* retain most recent unbalanced node and parent */
1627 if (cur->bf != 0)
1628 {
1629 last_unbal = cur;
1630 last_unbal_par = par;
1631 }
1632
1633 /* compare for insertion point */
1634 assert((cur->bf >= -1) && (cur->bf <= 1));
1635 par = cur;
1636 switch (val=(*cmp)(node,cur))
1637 {
1638 case -1: SET_TRAVERSE(tree,cur,lss); /* lss */
1639 cur = cur->lss; break;
1640 case 0: SET_TRAVERSE(tree,cur,self);/* match; leave ptr to node */
1641 return rvm_false;
1642 case 1: SET_TRAVERSE(tree,NULL,gtr); /* gtr */
1643 cur = cur->gtr; break;
1644 default: assert(rvm_false);
1645 }
1646 }
1647 /* insert node */
1648 if (val == 1)
1649 par->gtr = node;
1650 else
1651 par->lss = node;
1652 tree->n_nodes++;
1653
1654 /* determine side of possible imbalance and set new balance factor */
1655 if ((new_bf=(*cmp)(node,last_unbal)) == 1)
1656 sub_root = last_unbal->gtr;
1657 else
1658 sub_root = last_unbal->lss;
1659
1660 /* set balance factors of sub-tree, all of which must have been 0 */
1661 cur = sub_root;
1662 while (cur != node)
1663 {
1664 assert(cur->bf == 0);
1665 if ((cur->bf=(*cmp)(node,cur)) == 1)
1666 cur = cur->gtr;
1667 else
1668 cur = cur->lss;
1669 }
1670
1671 /* set balance factor of first unbalanced node; check for imbalance */
1672 if (last_unbal->bf == 0)
1673 {
1674 last_unbal->bf = new_bf;
1675 tree->level++;
1676 }
1677 else
1678 if ((last_unbal->bf+new_bf) == 0)
1679 last_unbal->bf = 0;
1680 else /* tree unbalanced: rotate */
1681 insert_rotate(tree,last_unbal,last_unbal_par,
1682 sub_root,new_bf);
1683
1684 /* record maximum depth */
1685 if ((tree->level+1) > tree->max_depth)
1686 tree->max_depth = tree->level+1;
1687
1688 return rvm_true;
1689 }
1690 /* deletion rotation function */
delete_rotate(tree,bal_pnt,bal_pnt_par,sub_root,new_bf)1691 static rvm_bool_t delete_rotate(tree,bal_pnt,bal_pnt_par,sub_root,new_bf)
1692 tree_root_t *tree; /* ptr to root of tree */
1693 tree_node_t *bal_pnt; /* balance point */
1694 tree_node_t *bal_pnt_par; /* parent of bal_pnt */
1695 tree_node_t *sub_root; /* root of unbalanced sub-tree */
1696 long new_bf; /* new balance factor */
1697 {
1698 tree_node_t *new_bal_pnt = sub_root; /* new balance point */
1699 long old_sub_root_bf = sub_root->bf;
1700
1701 assert(tree->struct_id == tree_root_id);
1702 if (new_bf == 1)
1703 { /* right heavy */
1704 if ((sub_root->bf == 1)
1705 || ((sub_root->bf == 0) && (sub_root->lss->bf == -1)))
1706 { /* RR rotations */
1707 bal_pnt->gtr = sub_root->lss;
1708 sub_root->lss = bal_pnt;
1709 if (sub_root->bf == 1)
1710 bal_pnt->bf = sub_root->bf = 0;
1711 else
1712 {
1713 bal_pnt->bf = 1;
1714 sub_root->bf = -1;
1715 }
1716 }
1717 else
1718 { /* RL rotations */
1719 new_bal_pnt = sub_root->lss;
1720 sub_root->lss = new_bal_pnt->gtr;
1721 bal_pnt->gtr = new_bal_pnt->lss;
1722 new_bal_pnt->gtr = sub_root;
1723 new_bal_pnt->lss = bal_pnt;
1724
1725 /* adjust balance factors */
1726 switch (new_bal_pnt->bf)
1727 {
1728 case 0: bal_pnt->bf = 0; sub_root->bf++;
1729 break;
1730 case 1: bal_pnt->bf = -1; sub_root->bf++;
1731 break;
1732 case -1: bal_pnt->bf = 0; sub_root->bf = 1;
1733 break;
1734 default: assert(rvm_false);
1735 }
1736 if (old_sub_root_bf == 0) new_bal_pnt->bf = 1;
1737 else new_bal_pnt->bf = 0;
1738 }
1739 }
1740 else
1741 { /* left heavy */
1742 if ((sub_root->bf == -1)
1743 || ((sub_root->bf == 0) && (sub_root->gtr->bf == 1)))
1744 { /* LL rotations */
1745 bal_pnt->lss = sub_root->gtr;
1746 sub_root->gtr = bal_pnt;
1747 if (sub_root->bf == -1)
1748 bal_pnt->bf = sub_root->bf = 0;
1749 else
1750 {
1751 bal_pnt->bf = -1;
1752 sub_root->bf = 1;
1753 }
1754 }
1755 else
1756 { /* LR rotations */
1757 new_bal_pnt = sub_root->gtr;
1758 sub_root->gtr = new_bal_pnt->lss;
1759 bal_pnt->lss = new_bal_pnt->gtr;
1760 new_bal_pnt->lss = sub_root;
1761 new_bal_pnt->gtr = bal_pnt;
1762
1763 /* adjust balance factors */
1764 switch (new_bal_pnt->bf)
1765 {
1766 case 0: bal_pnt->bf = 0; sub_root->bf--;
1767 break;
1768 case 1: bal_pnt->bf = 0; sub_root->bf = -1;
1769 break;
1770 case -1: bal_pnt->bf = 1; sub_root->bf--;
1771 break;
1772 default: assert(rvm_false);
1773 }
1774 if (old_sub_root_bf == 0) new_bal_pnt->bf = -1;
1775 else new_bal_pnt->bf = 0;
1776 }
1777 }
1778 /* complete rotation by re-inserting balanced sub-tree */
1779 if (bal_pnt_par == NULL)
1780 tree->root = new_bal_pnt;
1781 else
1782 if (bal_pnt == bal_pnt_par->gtr)
1783 bal_pnt_par->gtr = new_bal_pnt;
1784 else
1785 if (bal_pnt == bal_pnt_par->lss)
1786 bal_pnt_par->lss = new_bal_pnt;
1787
1788 /* return true if depth changed */
1789 if (new_bal_pnt->bf == 0)
1790 return rvm_true;
1791 return rvm_false;
1792 }
1793 /* binary tree deletion -- does not free the node
1794 traverse vector not left suitable for iterators */
tree_delete(tree,node,cmp)1795 rvm_bool_t tree_delete(tree,node,cmp)
1796 tree_root_t *tree; /* ptr to root of tree */
1797 tree_node_t *node; /* node to delete */
1798 cmp_func_t *cmp; /* comparator */
1799 {
1800 tree_node_t *cur; /* current search node */
1801 tree_node_t *sub_root=NULL; /* unbalanced sub tree root */
1802 tree_node_t *bal_pnt_par; /* parent of balance point */
1803 tree_node_t *old_root = tree->root; /* save state of old root */
1804 long old_root_bf = tree->root->bf;
1805 int node_level; /* level at which node found */
1806 long new_bf=0; /* new balance factor */
1807
1808 /* search for target node */
1809 assert(tree->struct_id == tree_root_id);
1810 chk_traverse(tree);
1811 tree->level = -1;
1812 cur = tree->root;
1813 while (cur != NULL)
1814 {
1815 /* determine branch to follow */
1816 assert((cur->bf >= -1) && (cur->bf <= 1));
1817 switch ((*cmp)(node,cur))
1818 {
1819 case -1: /* lss */
1820 SET_TRAVERSE(tree,cur,lss);
1821 cur = cur->lss;
1822 break;
1823 case 0:
1824 SET_TRAVERSE(tree,cur,self);
1825 if (cur == node) goto delete; /* located */
1826 assert(rvm_false); /* multiple entries ?!?! */
1827 case 1: /* gtr */
1828 SET_TRAVERSE(tree,cur,gtr);
1829 cur = cur->gtr;
1830 break;
1831 default: assert(rvm_false);
1832 }
1833 }
1834
1835 return rvm_false; /* not found */
1836 /* see if simple delete: node has <= 1 child */
1837 delete:
1838 tree->n_nodes--;
1839 node_level = tree->level;
1840 if (node->lss == NULL)
1841 {
1842 cur = node->gtr;
1843 tree->traverse[tree->level].state = gtr;
1844 }
1845 else if (node->gtr == NULL)
1846 {
1847 cur = node->lss;
1848 tree->traverse[tree->level].state = lss;
1849 }
1850 else
1851 {
1852 /* must select replacement node - use deeper side if possible,
1853 otherwise choose alternately with depth */
1854 if ((new_bf = node->bf) == 0)
1855 {
1856 new_bf = tree->level & 1;
1857 if (new_bf == 0) new_bf = -1;
1858 }
1859 if (new_bf == 1)
1860 {
1861 cur = node->gtr; /* locate successor */
1862 tree->traverse[tree->level].state = gtr;
1863 }
1864 else
1865 {
1866 cur = node->lss; /* locate predecessor */
1867 tree->traverse[tree->level].state = lss;
1868 }
1869 while (cur != NULL)
1870 {
1871 assert((cur->bf >= -1) && (cur->bf <= 1));
1872 if (new_bf == 1)
1873 {
1874 SET_TRAVERSE(tree,cur,lss);
1875 cur = cur->lss;
1876 }
1877 else
1878 {
1879 SET_TRAVERSE(tree,cur,gtr);
1880 cur = cur->gtr;
1881 }
1882 }
1883 /* unlink selected node */
1884 if (tree->level == 0)
1885 {
1886 cur = tree->root;
1887 if (new_bf == 1)
1888 tree->root = cur->gtr;
1889 else
1890 tree->root = cur->lss;
1891 }
1892 else
1893 {
1894 if (new_bf == 1)
1895 cur = tree->traverse[tree->level].ptr->gtr;
1896 else
1897 cur = tree->traverse[tree->level].ptr->lss;
1898 if (tree->traverse[tree->level-1].state == lss)
1899 tree->traverse[tree->level-1].ptr->lss = cur;
1900 else
1901 tree->traverse[tree->level-1].ptr->gtr = cur;
1902 cur = tree->traverse[tree->level].ptr;
1903 }
1904
1905 /* update selected node's state with target state */
1906 cur->bf = node->bf;
1907 cur->gtr = node->gtr;
1908 cur->lss = node->lss;
1909 }
1910
1911 /* delete target node */
1912 if (node_level == 0)
1913 tree->root = cur;
1914 else
1915 if (tree->traverse[node_level-1].state == lss)
1916 tree->traverse[node_level-1].ptr->lss = cur;
1917 else
1918 tree->traverse[node_level-1].ptr->gtr = cur;
1919 tree->traverse[node_level].ptr = cur;
1920 /* rebalance as necessary up path */
1921 while (--tree->level >= 0)
1922 {
1923 switch (tree->traverse[tree->level].state)
1924 {
1925 case lss:
1926 new_bf = 1;
1927 sub_root = tree->traverse[tree->level].ptr->gtr;
1928 break;
1929 case gtr:
1930 new_bf = -1;
1931 sub_root = tree->traverse[tree->level].ptr->lss;
1932 break;
1933 case self:
1934 default: assert(rvm_false);
1935 }
1936
1937 /* if tree balanced at this point, set new factor and quit */
1938 if (tree->traverse[tree->level].ptr->bf == 0)
1939 {
1940 tree->traverse[tree->level].ptr->bf = new_bf;
1941 break;
1942 }
1943 if ((tree->traverse[tree->level].ptr->bf+new_bf) == 0)
1944 {
1945 tree->traverse[tree->level].ptr->bf = 0;
1946 continue;
1947 }
1948
1949 /* must rotate to balance */
1950 if (tree->level == 0)
1951 bal_pnt_par = NULL;
1952 else
1953 bal_pnt_par = tree->traverse[tree->level-1].ptr;
1954 if (!delete_rotate(tree,tree->traverse[tree->level].ptr,
1955 bal_pnt_par,sub_root,new_bf))
1956 break; /* done, depth didn't change */
1957 }
1958
1959 /* adjust maximum height */
1960 if ((tree->root == NULL)
1961 || ((old_root == tree->root) && (old_root_bf != 0)
1962 && (tree->root->bf == 0))
1963 || ((old_root != tree->root) && (tree->root->bf == 0)))
1964 tree->max_depth--;
1965
1966 return rvm_true;
1967 }
1968 /* forward order iteration generator: balance not maintained if nodes unlinked */
tree_successor(tree)1969 tree_node_t *tree_successor(tree)
1970 tree_root_t *tree; /* ptr to tree root descriptor */
1971 {
1972 tree_node_t *cur; /* current search node */
1973
1974 /* determine how to continue */
1975 assert(tree->struct_id == tree_root_id);
1976
1977 DO_FOREVER
1978 {
1979 cur = tree->traverse[tree->level].ptr;
1980 if (cur != NULL)
1981 assert((cur->bf >= -1) && (cur->bf <= 1));
1982 switch (tree->traverse[tree->level].state)
1983 {
1984 case gtr:
1985 if (cur == NULL)
1986 {
1987 if (--tree->level < 0)
1988 return NULL;
1989 continue;
1990 }
1991 case lss:
1992 tree->traverse[tree->level].state = self;
1993 tree->traverse[tree->level].ptr = cur->gtr;
1994 goto unlink;
1995 case self:
1996 tree->traverse[tree->level].state = gtr;
1997 if (cur == NULL) continue;
1998 if (cur->lss != NULL) break;
1999 tree->traverse[tree->level].ptr = cur->gtr;
2000 goto unlink;
2001 case init:
2002 assert(tree->level == 0);
2003 tree->traverse[0].state = lss;
2004 break;
2005 default: assert(rvm_false);
2006 }
2007
2008 /* locate successor */
2009 while ((cur=cur->lss) != NULL)
2010 {
2011 assert((cur->bf >= -1) && (cur->bf <= 1));
2012 SET_TRAVERSE(tree,cur,lss);
2013 }
2014 }
2015 /* set next traverse node ptr */
2016 unlink:
2017 assert(cur != NULL);
2018 if (tree->unlink)
2019 {
2020 tree->n_nodes--;
2021 if (tree->level == 0)
2022 tree->root = cur->gtr;
2023 else
2024 tree->traverse[tree->level-1].ptr->lss = cur->gtr;
2025 assert(cur->lss == NULL);
2026 }
2027
2028 assert((cur->bf >= -1) && (cur->bf <= 1));
2029 return cur;
2030 }
2031 /* reverse order iterator generator: balance not maintained if nodes unlinked */
tree_predecessor(tree)2032 tree_node_t *tree_predecessor(tree)
2033 tree_root_t *tree; /* ptr to tree root descriptor */
2034 {
2035 tree_node_t *cur; /* current search node */
2036
2037 /* determine how to continue */
2038 assert(tree->struct_id == tree_root_id);
2039
2040 DO_FOREVER
2041 {
2042 cur = tree->traverse[tree->level].ptr;
2043 if (cur != NULL)
2044 assert((cur->bf >= -1) && (cur->bf <= 1));
2045 switch (tree->traverse[tree->level].state)
2046 {
2047 case lss:
2048 if (cur == NULL)
2049 {
2050 if (--tree->level < 0)
2051 return NULL;
2052 continue;
2053 }
2054 case gtr:
2055 tree->traverse[tree->level].state = self;
2056 tree->traverse[tree->level].ptr = cur->lss;
2057 goto unlink;
2058 case self:
2059 tree->traverse[tree->level].state = lss;
2060 if (cur == NULL) continue;
2061 if (cur->gtr != NULL) break;
2062 tree->traverse[tree->level].ptr = cur->lss;
2063 goto unlink;
2064 case init:
2065 assert(tree->level == 0);
2066 tree->traverse[0].state = gtr;
2067 break;
2068 default: assert(rvm_false);
2069 }
2070
2071 /* locate predecessor */
2072 while ((cur=cur->gtr) != NULL)
2073 {
2074 assert((cur->bf >= -1) && (cur->bf <= 1));
2075 SET_TRAVERSE(tree,cur,gtr);
2076 }
2077 }
2078 /* set next traverse node ptr */
2079 unlink:
2080 assert(cur != NULL);
2081 if (tree->unlink)
2082 {
2083 tree->n_nodes--;
2084 if (tree->level == 0)
2085 tree->root = cur->lss;
2086 else
2087 tree->traverse[tree->level-1].ptr->gtr = cur->lss;
2088 assert(cur->gtr == NULL);
2089 }
2090
2091 assert((cur->bf >= -1) && (cur->bf <= 1));
2092 return cur;
2093 }
2094 /* tree iteration initializers */
init_tree_generator(tree,direction,unlink)2095 tree_node_t *init_tree_generator(tree,direction,unlink)
2096 tree_root_t *tree; /* ptr to tree root descriptor */
2097 rvm_bool_t direction; /* FORWARD ==> lss -> gtr */
2098 rvm_bool_t unlink; /* unlink nodes from tree if true */
2099 {
2100
2101 assert(tree->struct_id == tree_root_id);
2102 tree->unlink = unlink;
2103 tree->level = -1;
2104 if (tree->root == NULL) return NULL;
2105 chk_traverse(tree);
2106 SET_TRAVERSE(tree,tree->root,init);
2107
2108 if (direction == FORWARD)
2109 return tree_successor(tree);
2110 else
2111 return tree_predecessor(tree);
2112 }
2113 /* initilizer for iteration after insertion failure */
tree_iterate_insert(tree,node,cmp)2114 tree_node_t *tree_iterate_insert(tree,node,cmp)
2115 tree_root_t *tree; /* ptr to root of tree */
2116 tree_node_t *node; /* node to insert */
2117 cmp_func_t *cmp; /* comparator */
2118 {
2119 tree_node_t *cur; /* current search node */
2120 int first_level; /* level of smallest node */
2121
2122 /* try to insert node */
2123 assert(tree->struct_id == tree_root_id);
2124 tree->unlink = rvm_false;
2125 if (tree_insert(tree,node,cmp))
2126 return NULL; /* done, no iteration required */
2127
2128 /* collision, locate smallest conflicting node */
2129 first_level = tree->level;
2130 cur = tree->traverse[tree->level].ptr->lss;
2131 tree->traverse[tree->level].state = lss;
2132 while (cur != NULL)
2133 switch ((*cmp)(cur,node))
2134 {
2135 case -1: SET_TRAVERSE(tree,NULL,gtr);
2136 cur = cur->gtr;
2137 break;
2138 case 0: SET_TRAVERSE(tree,cur,lss);
2139 first_level = tree->level;
2140 cur = cur->lss;
2141 break;
2142 case 1: /* shouldn't happen */
2143 default: assert(rvm_false);
2144 }
2145
2146 /* return smallest conflicting node */
2147 tree->level = first_level;
2148 cur = tree->traverse[tree->level].ptr;
2149 tree->traverse[tree->level].ptr = cur->gtr;
2150 tree->traverse[tree->level].state = self;
2151
2152 return cur;
2153 }
2154 /* histogram data gathering function */
enter_histogram(val,histo,histo_def,length)2155 void enter_histogram(val,histo,histo_def,length)
2156 long val; /* value to log */
2157 long *histo; /* histogram data */
2158 long *histo_def; /* histogram bucket sizes */
2159 long length; /* length of histogram vectors */
2160 {
2161 long i;
2162
2163 /* increment proper bucket */
2164 for (i=0; i<length-1; i++)
2165 if (val <= histo_def[i])
2166 {
2167 histo[i]++;
2168 return;
2169 }
2170
2171 histo[length-1]++; /* outsized */
2172 return;
2173 }
2174 /* The following functions are needed only on machines without 64-bit
2175 integer operations and are used only within macros defined in rvm.h
2176 */
2177 /* rvm_offset_t constructor */
rvm_mk_offset(x,y)2178 rvm_offset_t rvm_mk_offset(x,y)
2179 rvm_length_t x;
2180 rvm_length_t y;
2181 {
2182 rvm_offset_t tmp;
2183
2184 tmp.high = x;
2185 tmp.low = y;
2186
2187 return tmp;
2188 }
2189
2190 /* add rvm_length to rvm_offset; return (offset + length) */
rvm_add_length_to_offset(offset,length)2191 rvm_offset_t rvm_add_length_to_offset(offset,length)
2192 rvm_offset_t *offset; /* ptr to offset */
2193 rvm_length_t length;
2194 {
2195 rvm_offset_t tmp;
2196
2197 tmp.high = offset->high;
2198 tmp.low = offset->low + length;
2199 if (tmp.low < offset->low) /* test for overflow */
2200 tmp.high ++; /* do carry */
2201
2202 return tmp;
2203 }
2204
2205 /* subtract rvm_length from rvm_offset; return (offset - length)) */
rvm_sub_length_from_offset(offset,length)2206 rvm_offset_t rvm_sub_length_from_offset(offset,length)
2207 rvm_offset_t *offset; /* ptr to offset */
2208 rvm_length_t length; /* length to subtract */
2209 {
2210 rvm_offset_t tmp;
2211
2212 tmp.high = offset->high;
2213 tmp.low = offset->low - length;
2214 if (tmp.low > offset->low) /* test for underflow */
2215 tmp.high --; /* do borrow */
2216
2217 return tmp;
2218 }
2219 /* add rvm_offset to rvm_offset; return (x+y) */
rvm_add_offsets(x,y)2220 rvm_offset_t rvm_add_offsets(x,y)
2221 rvm_offset_t *x,*y; /* operand ptrs */
2222 {
2223 rvm_offset_t tmp;
2224
2225 tmp.high = x->high + y->high; /* add high order bits */
2226 tmp.low = x->low + y->low; /* add low order bits */
2227 if (tmp.low < x->low) /* test for overflow */
2228 tmp.high ++; /* do carry */
2229
2230 return tmp;
2231 }
2232
2233 /* subtract rvm_offset from rvm_offset; return (x-y) */
rvm_sub_offsets(x,y)2234 rvm_offset_t rvm_sub_offsets(x,y)
2235 rvm_offset_t *x,*y; /* operand ptrs */
2236 {
2237 rvm_offset_t tmp;
2238
2239 tmp.high = x->high - y->high; /* subtract high order bits */
2240 tmp.low = x->low - y->low; /* subtract low order bits */
2241 if (tmp.low > x->low) /* test for underflow */
2242 tmp.high --; /* do borrow */
2243
2244
2245 return tmp;
2246 }
2247 /* page rounding functions for rvm_offset; return offset rounded up/down
2248 to page boundrary: used only for rvm.h macro support */
rvm_rnd_offset_up_to_page(x)2249 rvm_offset_t rvm_rnd_offset_up_to_page(x)
2250 rvm_offset_t *x; /* operand ptr */
2251 {
2252 rvm_offset_t tmp;
2253
2254 tmp = rvm_add_length_to_offset(x,page_size-1);
2255 tmp.low = tmp.low & page_mask;
2256
2257 return tmp;
2258 }
2259
rvm_rnd_offset_dn_to_page(x)2260 rvm_offset_t rvm_rnd_offset_dn_to_page(x)
2261 rvm_offset_t *x; /* operand ptr */
2262 {
2263 rvm_offset_t tmp;
2264
2265 tmp.high = x->high;
2266 tmp.low = x->low & page_mask;
2267
2268 return tmp;
2269 }
2270
2271 /* page size, mask export functions: used only for rvm.h macros */
rvm_page_size()2272 rvm_length_t rvm_page_size()
2273 {
2274 return page_size;
2275 }
2276
rvm_page_mask()2277 rvm_length_t rvm_page_mask()
2278 {
2279 return page_mask;
2280 }
2281
2282 /* round offset to sector size support */
rvm_rnd_offset_to_sector(x)2283 rvm_offset_t rvm_rnd_offset_to_sector(x)
2284 rvm_offset_t *x;
2285 {
2286 rvm_offset_t tmp;
2287
2288 tmp = RVM_ADD_LENGTH_TO_OFFSET((*x),SECTOR_SIZE-1);
2289 tmp.low = tmp.low & (SECTOR_MASK);
2290
2291 return tmp;
2292 }
2293