Deleted Added
sdiff udiff text old ( 245254 ) new ( 246430 )
full compact
vm_radix.c (245254) vm_radix.c (246430)
1/*
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:

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

287 int height)
288{
289 uintptr_t root;
290
291 root = (uintptr_t)rnode | height;
292 rtree->rt_root = root;
293}
294
1/*
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:

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

287 int height)
288{
289 uintptr_t root;
290
291 root = (uintptr_t)rnode | height;
292 rtree->rt_root = root;
293}
294
295static inline void *
295static inline vm_page_t
296vm_radix_match(void *child)
297{
298 uintptr_t c;
299
300 c = (uintptr_t)child;
301
296vm_radix_match(void *child)
297{
298 uintptr_t c;
299
300 c = (uintptr_t)child;
301
302 return ((void *)(c & ~VM_RADIX_FLAGS));
302 return ((vm_page_t)(c & ~VM_RADIX_FLAGS));
303}
304
305static void
306vm_radix_reclaim_allnodes_internal(struct vm_radix_node *rnode, int level)
307{
308 int slot;
309
310 MPASS(rnode != NULL && level >= 0);

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

333 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level);
334 vm_radix_node_put(rnode);
335}
336
337/*
338 * Inserts the key-value pair in to the radix tree. Returns errno.
339 * Panics if the key already exists.
340 */
303}
304
305static void
306vm_radix_reclaim_allnodes_internal(struct vm_radix_node *rnode, int level)
307{
308 int slot;
309
310 MPASS(rnode != NULL && level >= 0);

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

333 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level);
334 vm_radix_node_put(rnode);
335}
336
337/*
338 * Inserts the key-value pair in to the radix tree. Returns errno.
339 * Panics if the key already exists.
340 */
341int
342vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val)
341void
342vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, vm_page_t page)
343{
344 struct vm_radix_node *rnode;
345 struct vm_radix_node *root;
346 int level;
347 int slot;
348
349 CTR4(KTR_VM,
343{
344 struct vm_radix_node *rnode;
345 struct vm_radix_node *root;
346 int level;
347 int slot;
348
349 CTR4(KTR_VM,
350 "insert: tree %p, " KFRMT64(index) ", val %p", rtree,
351 KSPLT64L(index), KSPLT64H(index), val);
350 "insert: tree %p, " KFRMT64(index) ", page %p", rtree,
351 KSPLT64L(index), KSPLT64H(index), page);
352 if (index == -1)
353 panic("vm_radix_insert: -1 is not a valid index.\n");
354 level = vm_radix_height(rtree, &root);
355 /*
356 * Increase the height by adding nodes at the root until
357 * there is sufficient space.
358 */
359 while (level == 0 || index > VM_RADIX_MAX(level)) {

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

371 */
372 if (root == NULL || root->rn_count != 0) {
373 rnode = vm_radix_node_get();
374 if (rnode == NULL) {
375 CTR5(KTR_VM,
376 "insert: tree %p, root %p, " KFRMT64(index) ", level %d ENOMEM",
377 rtree, root, KSPLT64L(index),
378 KSPLT64H(index), level);
352 if (index == -1)
353 panic("vm_radix_insert: -1 is not a valid index.\n");
354 level = vm_radix_height(rtree, &root);
355 /*
356 * Increase the height by adding nodes at the root until
357 * there is sufficient space.
358 */
359 while (level == 0 || index > VM_RADIX_MAX(level)) {

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

371 */
372 if (root == NULL || root->rn_count != 0) {
373 rnode = vm_radix_node_get();
374 if (rnode == NULL) {
375 CTR5(KTR_VM,
376 "insert: tree %p, root %p, " KFRMT64(index) ", level %d ENOMEM",
377 rtree, root, KSPLT64L(index),
378 KSPLT64H(index), level);
379 return (ENOMEM);
379 panic("vm_radix_insert: failed allocation");
380 }
381 /*
382 * Store the new pointer with a memory barrier so
383 * that it is visible before the new root.
384 */
385 if (root) {
386 atomic_store_rel_ptr((volatile uintptr_t *)
387 &rnode->rn_child[0], (uintptr_t)root);

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

403 CTR6(KTR_VM,
404 "insert: tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p ENOMEM",
405 rtree, KSPLT64L(index), KSPLT64H(index),
406 level, slot, rnode);
407 CTR4(KTR_VM,
408 "insert: tree %p, rnode %p, child %p, count %u ENOMEM",
409 rtree, rnode, rnode->rn_child[slot],
410 rnode->rn_count);
380 }
381 /*
382 * Store the new pointer with a memory barrier so
383 * that it is visible before the new root.
384 */
385 if (root) {
386 atomic_store_rel_ptr((volatile uintptr_t *)
387 &rnode->rn_child[0], (uintptr_t)root);

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

403 CTR6(KTR_VM,
404 "insert: tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p ENOMEM",
405 rtree, KSPLT64L(index), KSPLT64H(index),
406 level, slot, rnode);
407 CTR4(KTR_VM,
408 "insert: tree %p, rnode %p, child %p, count %u ENOMEM",
409 rtree, rnode, rnode->rn_child[slot],
410 rnode->rn_count);
411 return (ENOMEM);
411 panic("vm_radix_insert: failed allocation");
412 }
413 rnode->rn_count++;
414 }
415 CTR6(KTR_VM,
416 "insert: tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p",
417 rtree, KSPLT64L(index), KSPLT64H(index), level, slot,
418 rnode);
419 CTR4(KTR_VM,
420 "insert: tree %p, rnode %p, child %p, count %u",
421 rtree, rnode, rnode->rn_child[slot], rnode->rn_count);
422 rnode = rnode->rn_child[slot];
423 }
424
425 slot = vm_radix_slot(index, 0);
426 MPASS(rnode != NULL);
427 KASSERT(rnode->rn_child[slot] == NULL,
428 ("vm_radix_insert: Duplicate value %p at index: %lu\n",
429 rnode->rn_child[slot], (u_long)index));
412 }
413 rnode->rn_count++;
414 }
415 CTR6(KTR_VM,
416 "insert: tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p",
417 rtree, KSPLT64L(index), KSPLT64H(index), level, slot,
418 rnode);
419 CTR4(KTR_VM,
420 "insert: tree %p, rnode %p, child %p, count %u",
421 rtree, rnode, rnode->rn_child[slot], rnode->rn_count);
422 rnode = rnode->rn_child[slot];
423 }
424
425 slot = vm_radix_slot(index, 0);
426 MPASS(rnode != NULL);
427 KASSERT(rnode->rn_child[slot] == NULL,
428 ("vm_radix_insert: Duplicate value %p at index: %lu\n",
429 rnode->rn_child[slot], (u_long)index));
430 rnode->rn_child[slot] = val;
430 rnode->rn_child[slot] = page;
431 rnode->rn_count++;
432 CTR5(KTR_VM,
433 "insert: tree %p, " KFRMT64(index) ", level %d, slot %d",
434 rtree, KSPLT64L(index), KSPLT64H(index), level, slot);
435 CTR3(KTR_VM, "insert: slot %d, rnode %p, count %u", slot, rnode,
436 rnode->rn_count);
431 rnode->rn_count++;
432 CTR5(KTR_VM,
433 "insert: tree %p, " KFRMT64(index) ", level %d, slot %d",
434 rtree, KSPLT64L(index), KSPLT64H(index), level, slot);
435 CTR3(KTR_VM, "insert: slot %d, rnode %p, count %u", slot, rnode,
436 rnode->rn_count);
437
438 return 0;
439}
440
441/*
442 * Returns the value stored at the index. If the index is not present
443 * NULL is returned.
444 */
437}
438
439/*
440 * Returns the value stored at the index. If the index is not present
441 * NULL is returned.
442 */
445void *
443vm_page_t
446vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index)
447{
448 struct vm_radix_node *rnode;
449 int slot;
450 int level;
451
452 level = vm_radix_height(rtree, &rnode);
453 if (index > VM_RADIX_MAX(level))

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

546out:
547 *startp = start;
548 return (rnode);
549}
550
551/*
552 * Look up any entry at a position bigger than or equal to index.
553 */
444vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index)
445{
446 struct vm_radix_node *rnode;
447 int slot;
448 int level;
449
450 level = vm_radix_height(rtree, &rnode);
451 if (index > VM_RADIX_MAX(level))

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

544out:
545 *startp = start;
546 return (rnode);
547}
548
549/*
550 * Look up any entry at a position bigger than or equal to index.
551 */
554void *
555vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t start)
552vm_page_t
553vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index)
556{
554{
555 vm_page_t page;
557 struct vm_radix_node *rnode;
556 struct vm_radix_node *rnode;
558 void *val;
559 int slot;
560
557 int slot;
558
561 CTR3(KTR_VM, "lookupn: tree %p, " KFRMT64(start), rtree,
562 KSPLT64L(start), KSPLT64H(start));
559 CTR3(KTR_VM, "lookupn: tree %p, " KFRMT64(index), rtree,
560 KSPLT64L(index), KSPLT64H(index));
563 if (rtree->rt_root == 0)
564 return (NULL);
561 if (rtree->rt_root == 0)
562 return (NULL);
565 while ((rnode = vm_radix_leaf(rtree, &start)) != NULL) {
566 slot = vm_radix_slot(start, 0);
567 for (; slot < VM_RADIX_COUNT; slot++, start++) {
568 val = vm_radix_match(rnode->rn_child[slot]);
569 if (val == NULL) {
563 while ((rnode = vm_radix_leaf(rtree, &index)) != NULL) {
564 slot = vm_radix_slot(index, 0);
565 for (; slot < VM_RADIX_COUNT; slot++, index++) {
566 page = vm_radix_match(rnode->rn_child[slot]);
567 if (page == NULL) {
570
571 /*
568
569 /*
572 * The start address can wrap at the
570 * The index address can wrap at the
573 * VM_RADIX_MAXVAL value.
571 * VM_RADIX_MAXVAL value.
574 * We need to make sure that start address
572 * We need to make sure that index address
575 * point to the next chunk (even if wrapping)
576 * to stay consistent with default scanning
577 * behaviour. Also, because of the nature
578 * of the wrapping, the wrap up checks must
579 * be done after all the necessary controls
573 * point to the next chunk (even if wrapping)
574 * to stay consistent with default scanning
575 * behaviour. Also, because of the nature
576 * of the wrapping, the wrap up checks must
577 * be done after all the necessary controls
580 * on start are completed.
578 * on index are completed.
581 */
579 */
582 if ((VM_RADIX_MAXVAL - start) == 0)
580 if ((VM_RADIX_MAXVAL - index) == 0)
583 return (NULL);
584 continue;
585 }
586 CTR5(KTR_VM,
587 "lookupn: tree %p " KFRMT64(index) " slot %d found child %p",
581 return (NULL);
582 continue;
583 }
584 CTR5(KTR_VM,
585 "lookupn: tree %p " KFRMT64(index) " slot %d found child %p",
588 rtree, KSPLT64L(start), KSPLT64H(start), slot, val);
589 return (val);
586 rtree, KSPLT64L(index), KSPLT64H(index), slot,
587 page);
588 return (page);
590 }
589 }
591 MPASS((VM_RADIX_MAXVAL - start) != 0);
590 MPASS((VM_RADIX_MAXVAL - index) != 0);
592 }
593 return (NULL);
594}
595
596/*
597 * Look up any entry at a position less than or equal to index.
598 */
591 }
592 return (NULL);
593}
594
595/*
596 * Look up any entry at a position less than or equal to index.
597 */
599void *
598vm_page_t
600vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
601{
602 struct vm_radix_node *rnode;
603 struct vm_radix_node *child;
604 vm_pindex_t max;
605 vm_pindex_t inc;
599vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
600{
601 struct vm_radix_node *rnode;
602 struct vm_radix_node *child;
603 vm_pindex_t max;
604 vm_pindex_t inc;
606 void *val;
605 vm_page_t page;
607 int slot;
608 int level;
609
610 CTR3(KTR_VM, "lookup_le: tree %p, " KFRMT64(index), rtree,
611 KSPLT64L(index), KSPLT64H(index));
612restart:
613 level = vm_radix_height(rtree, &rnode);
614 if (rnode == NULL)

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

656 break;
657 }
658 }
659 rnode = child;
660 level--;
661 }
662 if (rnode) {
663 for (; slot >= 0; slot--, index--) {
606 int slot;
607 int level;
608
609 CTR3(KTR_VM, "lookup_le: tree %p, " KFRMT64(index), rtree,
610 KSPLT64L(index), KSPLT64H(index));
611restart:
612 level = vm_radix_height(rtree, &rnode);
613 if (rnode == NULL)

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

655 break;
656 }
657 }
658 rnode = child;
659 level--;
660 }
661 if (rnode) {
662 for (; slot >= 0; slot--, index--) {
664 val = vm_radix_match(rnode->rn_child[slot]);
665 if (val)
666 return (val);
663 page = vm_radix_match(rnode->rn_child[slot]);
664 if (page)
665 return (page);
667 }
668 }
669 if (index != -1)
670 goto restart;
671 return (NULL);
672}
673
674/*

--- 88 unchanged lines hidden --- 		666 }
667 }
668 if (index != -1)
669 goto restart;
670 return (NULL);
671}
672
673/*

--- 88 unchanged lines hidden ---