Lines Matching defs:pivot
27 /* Number of pivots in pivot allocator. */
30 * Max number (inclusive) of pages the pivot allocator
38 * Number of allocations that a pivot can supply before expiring.
39 * When a pivot expires, a new pivot has to be found.
67 * Definition of a pivot in pivot selector.
75 /* uvm_addr state for pivot selector. */
79 /* Free space tree, for fast pivot selection. */
903 * Select a new pivot.
905 * A pivot must:
910 * Furthermore, the pivot must provide sufficient space for the allocation.
917 struct uaddr_pivot *pivot,
936 panic("uaddr_pivot_newpivot: cannot grant random pivot "
1033 * Set up new pivot and return selected address.
1035 * Depending on the direction of the pivot, the pivot must be placed
1037 * - if the pivot moves upwards, place the pivot at the top of the
1039 * - if the pivot moves downwards, place the pivot at the bottom
1042 pivot->entry = found;
1043 pivot->dir = (arc4random() & 0x1 ? 1 : -1);
1044 if (pivot->dir > 0)
1045 pivot->addr = *addr_out + sz;
1047 pivot->addr = *addr_out;
1048 pivot->expire = PIVOT_EXPIRE - 1; /* First use is right now. */
1055 * Each time the selector is invoked, it will select a random pivot, which
1056 * it will use to select memory with. The memory will be placed at the pivot,
1057 * with a randomly sized gap between the allocation and the pivot.
1058 * The pivot will then move so it will never revisit this address.
1060 * Each allocation, the pivot expiry timer ticks. Once the pivot becomes
1061 * expired, it will be replaced with a newly created pivot. Pivots also
1065 * which will ensure the pivot points at memory in such a way that the
1068 * allocation immediately and move the pivot as appropriate.
1070 * If uaddr_pivot_newpivot() fails to find a new pivot that will allow the
1071 * allocation to succeed, it will not create a new pivot and the allocation
1074 * A pivot running into used memory will automatically expire (because it will
1094 struct uaddr_pivot *pivot;
1111 * Select a random pivot and a random gap sizes around the allocation.
1114 pivot = &uaddr->up_pivots[
1118 if (pivot->addr == 0 || pivot->entry == NULL || pivot->expire == 0)
1122 * Attempt to use the pivot to map the entry.
1124 entry = pivot->entry;
1125 if (pivot->dir > 0) {
1127 MAX(VMMAP_FREE_START(entry), pivot->addr),
1132 pivot->addr = min + sz;
1133 pivot->expire--;
1139 MIN(VMMAP_FREE_END(entry), pivot->addr),
1143 pivot->addr = max;
1144 pivot->expire--;
1152 * Use pivot selector to do the allocation and find a new pivot.
1154 err = uaddr_pivot_newpivot(map, uaddr, pivot, entry_out, addr_out,
1160 * Free the pivot.
1226 * Inform any pivot with this entry that the entry is gone.
1227 * Note that this does not automatically invalidate the pivot.
1237 * Create a new pivot selector.
1242 * - pivots select better on demand, because the pivot selection will be
1273 struct uaddr_pivot *pivot;
1281 pivot = &uaddr->up_pivots[i];
1284 pivot->addr, pivot->expire, pivot->dir);
1298 pivot = &uaddr->up_pivots[i];
1299 check_addr = pivot->addr;
1302 if (pivot->dir < 0)
1307 (*pr)("\t\tcontains pivot %d (0x%lx)\n",
1308 i, pivot->addr);