Deleted Added
sdiff udiff text old ( 226876 ) new ( 226930 )
full compact
vm_radix.c (226876) vm_radix.c (226930)
1/*
1/*
2 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
3 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
2 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
3 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright

--- 194 unchanged lines hidden (view full) ---

206 int height)
207{
208 uintptr_t root;
209
210 root = (uintptr_t)rnode | height;
211 rtree->rt_root = root;
212}
213
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright

--- 194 unchanged lines hidden (view full) ---

206 int height)
207{
208 uintptr_t root;
209
210 root = (uintptr_t)rnode | height;
211 rtree->rt_root = root;
212}
213
214static inline void *
215vm_radix_match(void *child, int color)
216{
217 uintptr_t c;
218
219 c = (uintptr_t)child;
220
221 if ((c & color) == 0)
222 return (NULL);
223 return ((void *)(c & ~VM_RADIX_FLAGS));
224}
225
214/*
215 * Inserts the key-value pair in to the radix tree. Returns errno.
216 * Panics if the key already exists.
217 */
218int
219vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val)
220{
221 struct vm_radix_node *rnode;

--- 50 unchanged lines hidden (view full) ---

272 rnode->rn_count++;
273 }
274 CTR5(KTR_VM,
275 "insert: tree %p, index %p, level %d, slot %d, child %p",
276 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
277 rnode = rnode->rn_child[slot];
278 }
279
226/*
227 * Inserts the key-value pair in to the radix tree. Returns errno.
228 * Panics if the key already exists.
229 */
230int
231vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val)
232{
233 struct vm_radix_node *rnode;

--- 50 unchanged lines hidden (view full) ---

284 rnode->rn_count++;
285 }
286 CTR5(KTR_VM,
287 "insert: tree %p, index %p, level %d, slot %d, child %p",
288 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
289 rnode = rnode->rn_child[slot];
290 }
291
280 slot = vm_radix_slot(index, level);
292 slot = vm_radix_slot(index, 0);
281 CTR5(KTR_VM, "insert: tree %p, index %p, level %d, slot %d, child %p",
282 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
283 KASSERT(rnode->rn_child[slot] == NULL,
284 ("vm_radix_insert: Duplicate value %p at index: %lu\n",
285 rnode->rn_child[slot], (u_long)index));
293 CTR5(KTR_VM, "insert: tree %p, index %p, level %d, slot %d, child %p",
294 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
295 KASSERT(rnode->rn_child[slot] == NULL,
296 ("vm_radix_insert: Duplicate value %p at index: %lu\n",
297 rnode->rn_child[slot], (u_long)index));
298 val = (void *)((uintptr_t)val | VM_RADIX_BLACK);
286 rnode->rn_child[slot] = val;
299 rnode->rn_child[slot] = val;
287 rnode->rn_count++;
300 atomic_add_int((volatile int *)&rnode->rn_count, 1);
288
289 return 0;
290}
291
292/*
293 * Returns the value stored at the index. If the index is not present
294 * NULL is returned.
295 */
296void *
301
302 return 0;
303}
304
305/*
306 * Returns the value stored at the index. If the index is not present
307 * NULL is returned.
308 */
309void *
297vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index)
310vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int color)
298{
299 struct vm_radix_node *rnode;
300 int slot;
301 int level;
302
303 level = vm_radix_height(rtree, &rnode);
304 if (index > VM_RADIX_MAX(level))
305 return NULL;
306 level--;
307 while (rnode) {
308 slot = vm_radix_slot(index, level);
309 CTR5(KTR_VM,
310 "lookup: tree %p, index %p, level %d, slot %d, child %p",
311 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
312 if (level == 0)
311{
312 struct vm_radix_node *rnode;
313 int slot;
314 int level;
315
316 level = vm_radix_height(rtree, &rnode);
317 if (index > VM_RADIX_MAX(level))
318 return NULL;
319 level--;
320 while (rnode) {
321 slot = vm_radix_slot(index, level);
322 CTR5(KTR_VM,
323 "lookup: tree %p, index %p, level %d, slot %d, child %p",
324 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
325 if (level == 0)
313 return rnode->rn_child[slot];
326 return vm_radix_match(rnode->rn_child[slot], color);
314 rnode = rnode->rn_child[slot];
315 level--;
316 }
317 CTR2(KTR_VM, "lookup: tree %p, index %p failed", rtree, (void *)index);
318
319 return NULL;
320}
321
327 rnode = rnode->rn_child[slot];
328 level--;
329 }
330 CTR2(KTR_VM, "lookup: tree %p, index %p failed", rtree, (void *)index);
331
332 return NULL;
333}
334
335void *
336vm_radix_color(struct vm_radix *rtree, vm_pindex_t index, int color)
337{
338 struct vm_radix_node *rnode;
339 uintptr_t child;
340 int slot;
341 int level;
342
343 level = vm_radix_height(rtree, &rnode);
344 if (index > VM_RADIX_MAX(level))
345 return NULL;
346 level--;
347 while (rnode) {
348 slot = vm_radix_slot(index, level);
349 CTR5(KTR_VM,
350 "color: tree %p, index %p, level %d, slot %d, child %p",
351 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
352 if (level == 0)
353 break;
354 rnode = rnode->rn_child[slot];
355 level--;
356 }
357 if (rnode == NULL || rnode->rn_child[slot] == NULL)
358 return (NULL);
359 child = (uintptr_t)rnode->rn_child[slot];
360 child &= ~VM_RADIX_FLAGS;
361 rnode->rn_child[slot] = (void *)(child | color);
362
363 return (void *)child;
364}
365
322/*
366/*
323 * Looks up as many as cnt values between start and end inclusive, and stores
324 * them in the caller allocated array out. The next index can be used to
325 * restart the scan. This optimizes forward scans in the tree.
367 * Looks up as many as cnt values between start and end, and stores
368 * them in the caller allocated array out. The next index can be used
369 * to restart the scan. This optimizes forward scans in the tree.
326 */
327int
328vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
370 */
371int
372vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
329 vm_pindex_t end, void **out, int cnt, vm_pindex_t *next)
373 vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next)
330{
331 struct vm_radix_node *rnode;
374{
375 struct vm_radix_node *rnode;
332 struct vm_radix_node *child;
333 vm_pindex_t max;
334 vm_pindex_t inc;
335 int slot;
336 int level;
337 void *val;
338 int outidx;
376 vm_pindex_t inc;
377 int slot;
378 int level;
379 void *val;
380 int outidx;
339 int loops = 0;
340
341 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p",
342 rtree, (void *)start, (void *)end);
343 outidx = 0;
344restart:
345 level = vm_radix_height(rtree, &rnode);
381
382 CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p",
383 rtree, (void *)start, (void *)end);
384 outidx = 0;
385restart:
386 level = vm_radix_height(rtree, &rnode);
346 max = VM_RADIX_MAX(level);
347 if (start > max)
387 if (rnode == NULL || start > VM_RADIX_MAX(level))
348 goto out;
388 goto out;
349 if (end > max || end == 0)
350 end = max;
351 loops++;
352 if (loops > 1000)
353 panic("vm_radix_lookupn: looping %d\n", loops);
389 if (end && start >= end)
390 goto out;
354 /*
355 * Search the tree from the top for any leaf node holding an index
356 * between start and end.
357 */
391 /*
392 * Search the tree from the top for any leaf node holding an index
393 * between start and end.
394 */
358 level--;
359 while (rnode) {
395 for (level--; level; level--) {
360 slot = vm_radix_slot(start, level);
361 CTR5(KTR_VM,
362 "lookupn: tree %p, index %p, level %d, slot %d, child %p",
363 rtree, (void *)start, level, slot, rnode->rn_child[slot]);
396 slot = vm_radix_slot(start, level);
397 CTR5(KTR_VM,
398 "lookupn: tree %p, index %p, level %d, slot %d, child %p",
399 rtree, (void *)start, level, slot, rnode->rn_child[slot]);
364 if (level == 0)
365 break;
400 if (rnode->rn_child[slot] != NULL) {
401 rnode = rnode->rn_child[slot];
402 continue;
403 }
366 /*
404 /*
367 * If we don't have an exact match we must start our search
368 * from the next leaf and adjust our index appropriately.
369 */
370 if ((child = rnode->rn_child[slot]) == NULL) {
371 /*
372 * Calculate how much to increment our index by
373 * based on the tree level. We must truncate the
374 * lower bits to start from the begnning of the next
375 * leaf.
376 */
377 inc = 1LL << (level * VM_RADIX_WIDTH);
378 start &= ~VM_RADIX_MAX(level);
379 start += inc;
380 slot++;
381 CTR5(KTR_VM,
382 "lookupn: start %p end %p inc %d mask 0x%lX slot %d",
383 (void *)start, (void *)end, inc, ~VM_RADIX_MAX(level), slot);
384 for (; slot < VM_RADIX_COUNT && start <= end;
385 slot++, start += inc) {
386 child = rnode->rn_child[slot];
387 if (child)
388 break;
405 * Calculate how much to increment our index by
406 * based on the tree level. We must truncate the
407 * lower bits to start from the begnning of the
408 * next leaf.
409 */
410 inc = 1LL << (level * VM_RADIX_WIDTH);
411 start &= ~VM_RADIX_MAX(level);
412 start += inc;
413 slot++;
414 CTR5(KTR_VM,
415 "lookupn: start %p end %p inc %d mask 0x%lX slot %d",
416 (void *)start, (void *)end, inc,
417 ~VM_RADIX_MAX(level), slot);
418 for (; slot < VM_RADIX_COUNT; slot++, start += inc) {
419 if (end != 0 && start >= end)
420 goto out;
421 if (rnode->rn_child[slot]) {
422 rnode = rnode->rn_child[slot];
423 break;
389 }
390 }
424 }
425 }
391 rnode = child;
392 level--;
393 }
394 if (rnode == NULL) {
395 /*
396 * If we still have another range to search, start looking
397 * from the next node. Otherwise, return what we've already
398 * found. The loop above has already adjusted start to the
399 * beginning of the next node.
400 *
401 * Detect start wrapping back to 0 and return in this case.
402 */
403 if (start <= end && start != 0)
426 if (slot == VM_RADIX_COUNT)
404 goto restart;
427 goto restart;
405 goto out;
406 }
428 }
407 for (; outidx < cnt && slot < VM_RADIX_COUNT && start <= end;
408 slot++, start++) {
409 val = rnode->rn_child[slot];
429 slot = vm_radix_slot(start, 0);
430 for (; slot < VM_RADIX_COUNT; slot++, start++) {
431 if (end != 0 && start >= end)
432 goto out;
433 val = vm_radix_match(rnode->rn_child[slot], color);
410 if (val == NULL)
411 continue;
434 if (val == NULL)
435 continue;
436 CTR4(KTR_VM,
437 "lookupn: tree %p index %p slot %d found child %p",
438 rtree, (void *)start, slot, val);
412 out[outidx++] = val;
439 out[outidx++] = val;
440 if (outidx == cnt)
441 goto out;
413 }
414 /*
415 * Go fetch the next page to fill the requested number of pages
416 * otherwise the caller will simply call us again to fulfill the
417 * same request after the structures are pushed out of cache.
418 */
442 }
443 /*
444 * Go fetch the next page to fill the requested number of pages
445 * otherwise the caller will simply call us again to fulfill the
446 * same request after the structures are pushed out of cache.
447 */
419 if (outidx < cnt && start <= end)
448 if ((end == 0 || start < end))
420 goto restart;
449 goto restart;
421
422out:
423 *next = start;
424
425 return (outidx);
426}
427
428/*
429 * Look up any entry at a position less than or equal to index.
430 */
431void *
450out:
451 *next = start;
452
453 return (outidx);
454}
455
456/*
457 * Look up any entry at a position less than or equal to index.
458 */
459void *
432vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
460vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color)
433{
434 struct vm_radix_node *rnode;
435 struct vm_radix_node *child;
436 vm_pindex_t max;
437 vm_pindex_t inc;
461{
462 struct vm_radix_node *rnode;
463 struct vm_radix_node *child;
464 vm_pindex_t max;
465 vm_pindex_t inc;
466 void *val;
438 int slot;
439 int level;
467 int slot;
468 int level;
440 int loops = 0;
441
442 CTR2(KTR_VM,
443 "lookup_le: tree %p, index %p", rtree, (void *)index);
444restart:
445 level = vm_radix_height(rtree, &rnode);
446 if (rnode == NULL)
447 return (NULL);
448 max = VM_RADIX_MAX(level);
449 if (index > max || index == 0)
450 index = max;
469
470 CTR2(KTR_VM,
471 "lookup_le: tree %p, index %p", rtree, (void *)index);
472restart:
473 level = vm_radix_height(rtree, &rnode);
474 if (rnode == NULL)
475 return (NULL);
476 max = VM_RADIX_MAX(level);
477 if (index > max || index == 0)
478 index = max;
451 loops++;
452 if (loops > 1000)
453 panic("vm_radix_looku_le: looping %d\n", loops);
454 /*
455 * Search the tree from the top for any leaf node holding an index
456 * lower than 'index'.
457 */
458 level--;
459 while (rnode) {
460 slot = vm_radix_slot(index, level);
461 CTR5(KTR_VM,

--- 25 unchanged lines hidden (view full) ---

487 break;
488 }
489 }
490 rnode = child;
491 level--;
492 }
493 if (rnode) {
494 for (; slot >= 0; slot--, index--) {
479 /*
480 * Search the tree from the top for any leaf node holding an index
481 * lower than 'index'.
482 */
483 level--;
484 while (rnode) {
485 slot = vm_radix_slot(index, level);
486 CTR5(KTR_VM,

--- 25 unchanged lines hidden (view full) ---

512 break;
513 }
514 }
515 rnode = child;
516 level--;
517 }
518 if (rnode) {
519 for (; slot >= 0; slot--, index--) {
495 if (rnode->rn_child[slot])
496 return (rnode->rn_child[slot]);
520 val = vm_radix_match(rnode->rn_child[slot], color);
521 if (val)
522 return (val);
497 }
498 }
499 if (index != -1)
500 goto restart;
501 return (NULL);
502}
503
504/*
505 * Remove the specified index from the tree. If possible the height of the
506 * tree is adjusted after deletion. The value stored at index is returned
507 * panics if the key is not present.
508 */
509void *
523 }
524 }
525 if (index != -1)
526 goto restart;
527 return (NULL);
528}
529
530/*
531 * Remove the specified index from the tree. If possible the height of the
532 * tree is adjusted after deletion. The value stored at index is returned
533 * panics if the key is not present.
534 */
535void *
510vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index)
536vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color)
511{
512 struct vm_radix_node *stack[VM_RADIX_LIMIT];
513 struct vm_radix_node *rnode, *root;
514 void *val;
515 int level;
516 int slot;
517
518 level = vm_radix_height(rtree, &root);

--- 10 unchanged lines hidden (view full) ---

529 stack[level] = rnode;
530 slot = vm_radix_slot(index, level);
531 rnode = rnode->rn_child[slot];
532 CTR5(KTR_VM,
533 "remove: tree %p, index %p, level %d, slot %d, child %p",
534 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
535 level--;
536 }
537{
538 struct vm_radix_node *stack[VM_RADIX_LIMIT];
539 struct vm_radix_node *rnode, *root;
540 void *val;
541 int level;
542 int slot;
543
544 level = vm_radix_height(rtree, &root);

--- 10 unchanged lines hidden (view full) ---

555 stack[level] = rnode;
556 slot = vm_radix_slot(index, level);
557 rnode = rnode->rn_child[slot];
558 CTR5(KTR_VM,
559 "remove: tree %p, index %p, level %d, slot %d, child %p",
560 rtree, (void *)index, level, slot, rnode->rn_child[slot]);
561 level--;
562 }
563 KASSERT(rnode != NULL,
564 ("vm_radix_remove: index %jd not present in the tree.\n", index));
537 slot = vm_radix_slot(index, 0);
565 slot = vm_radix_slot(index, 0);
538 KASSERT(rnode != NULL && rnode->rn_child[slot] != NULL,
566 val = vm_radix_match(rnode->rn_child[slot], color);
567 KASSERT(val != NULL,
539 ("vm_radix_remove: index %jd not present in the tree.\n", index));
540
568 ("vm_radix_remove: index %jd not present in the tree.\n", index));
569
541 val = rnode->rn_child[slot];
542 for (;;) {
543 rnode->rn_child[slot] = NULL;
570 for (;;) {
571 rnode->rn_child[slot] = NULL;
544 rnode->rn_count--;
545 if (rnode->rn_count > 0)
572 /*
573 * Use atomics for the last level since red and black
574 * will both adjust it.
575 */
576 if (level == 0)
577 atomic_add_int((volatile int *)&rnode->rn_count, -1);
578 else
579 rnode->rn_count--;
580 /*
581 * Only allow black removes to prune the tree.
582 */
583 if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0)
546 break;
547 vm_radix_node_put(rnode);
548 if (rnode == root) {
549 vm_radix_setroot(rtree, NULL, 0);
550 break;
551 }
552 rnode = stack[++level];
553 slot = vm_radix_slot(index, level);

--- 34 unchanged lines hidden --- 		584 break;
585 vm_radix_node_put(rnode);
586 if (rnode == root) {
587 vm_radix_setroot(rtree, NULL, 0);
588 break;
589 }
590 rnode = stack[++level];
591 slot = vm_radix_slot(index, level);

--- 34 unchanged lines hidden ---