Remove uaddr_hint allocator

The hint allocator would have to check that the
allocation does not overlap with brk, stack or text
areas. This would make the address selectors too
entagled. Just use the rnd allocator for hinted allocations
in case pivots are used. This also reduces the amount of code somewhat.

ok kettenis visa deraadt

3 files changed, 13 insertions, 144 deletions

diff --git a/sys/uvm/uvm_addr.c b/sys/uvm/uvm_addr.c
index 7913e615f45..af33700273b 100644
--- a/sys/uvm/uvm_addr.c
+++ b/sys/uvm/uvm_addr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_addr.c,v 1.22 2016/09/16 02:50:54 dlg Exp $	*/
+/*	$OpenBSD: uvm_addr.c,v 1.23 2017/01/17 17:19:21 stefan Exp $	*/
 
 /*
  * Copyright (c) 2011 Ariane van der Steldt <ariane@stack.nl>
@@ -46,17 +46,10 @@
 
 /* Pool with uvm_addr_state structures. */
 struct pool uaddr_pool;
-struct pool uaddr_hint_pool;
 struct pool uaddr_bestfit_pool;
 struct pool uaddr_pivot_pool;
 struct pool uaddr_rnd_pool;
 
-/* uvm_addr state for hint based selector. */
-struct uaddr_hint_state {
-	struct uvm_addr_state		 uaddr;
-	vsize_t				 max_dist;
-};
-
 /* uvm_addr state for bestfit selector. */
 struct uaddr_bestfit_state {
 	struct uvm_addr_state		 ubf_uaddr;
@@ -118,7 +111,6 @@ void			 uaddr_kremove(struct vm_map *,
 void			 uaddr_kbootstrapdestroy(struct uvm_addr_state *);
 
 void			 uaddr_destroy(struct uvm_addr_state *);
-void			 uaddr_hint_destroy(struct uvm_addr_state *);
 void			 uaddr_kbootstrap_destroy(struct uvm_addr_state *);
 void			 uaddr_rnd_destroy(struct uvm_addr_state *);
 void			 uaddr_bestfit_destroy(struct uvm_addr_state *);
@@ -138,10 +130,6 @@ int			 uaddr_rnd_select(struct vm_map *,
 			    struct uvm_addr_state *, struct vm_map_entry **,
 			    vaddr_t *, vsize_t, vaddr_t, vaddr_t, vm_prot_t,
 			    vaddr_t);
-int			 uaddr_hint_select(struct vm_map *,
-			    struct uvm_addr_state*, struct vm_map_entry **,
-			    vaddr_t *, vsize_t, vaddr_t, vaddr_t, vm_prot_t,
-			    vaddr_t);
 int			 uaddr_bestfit_select(struct vm_map *,
 			    struct uvm_addr_state*, struct vm_map_entry **,
 			    vaddr_t *, vsize_t, vaddr_t, vaddr_t, vm_prot_t,
@@ -290,8 +278,6 @@ uvm_addr_init(void)
 {
 	pool_init(&uaddr_pool, sizeof(struct uvm_addr_state), 0,
 	    IPL_VM, PR_WAITOK, "uaddr", NULL);
-	pool_init(&uaddr_hint_pool, sizeof(struct uaddr_hint_state), 0,
-	    IPL_VM, PR_WAITOK, "uaddrhint", NULL);
 	pool_init(&uaddr_bestfit_pool, sizeof(struct uaddr_bestfit_state), 0,
 	    IPL_VM, PR_WAITOK, "uaddrbest", NULL);
 	pool_init(&uaddr_pivot_pool, sizeof(struct uaddr_pivot_state), 0,
@@ -740,116 +726,6 @@ uaddr_rnd_print(struct uvm_addr_state *uaddr_p, boolean_t full,
 #endif
 
 /*
- * An allocator that selects an address within distance of the hint.
- *
- * If no hint is given, the allocator refuses to allocate.
- */
-const struct uvm_addr_functions uaddr_hint_functions = {
-	.uaddr_select = &uaddr_hint_select,
-	.uaddr_destroy = &uaddr_hint_destroy,
-	.uaddr_name = "uaddr_hint"
-};
-
-/*
- * Create uaddr_hint state.
- */
-struct uvm_addr_state *
-uaddr_hint_create(vaddr_t minaddr, vaddr_t maxaddr, vsize_t max_dist)
-{
-	struct uaddr_hint_state *ua_hint;
-
-	KASSERT(uaddr_hint_pool.pr_size == sizeof(*ua_hint));
-
-	ua_hint = pool_get(&uaddr_hint_pool, PR_WAITOK);
-	ua_hint->uaddr.uaddr_minaddr = minaddr;
-	ua_hint->uaddr.uaddr_maxaddr = maxaddr;
-	ua_hint->uaddr.uaddr_functions = &uaddr_hint_functions;
-	ua_hint->max_dist = max_dist;
-	return &ua_hint->uaddr;
-}
-
-/*
- * Destroy uaddr_hint state.
- */
-void
-uaddr_hint_destroy(struct uvm_addr_state *uaddr)
-{
-	pool_put(&uaddr_hint_pool, uaddr);
-}
-
-/*
- * Hint selector.
- *
- * Attempts to find an address that is within max_dist of the hint.
- */
-int
-uaddr_hint_select(struct vm_map *map, struct uvm_addr_state *uaddr_param,
-    struct vm_map_entry **entry_out, vaddr_t *addr_out,
-    vsize_t sz, vaddr_t align, vaddr_t offset,
-    vm_prot_t prot, vaddr_t hint)
-{
-	struct uaddr_hint_state	*uaddr =
-	    (struct uaddr_hint_state *)uaddr_param;
-	vsize_t			 before_gap, after_gap;
-	vaddr_t			 low, high;
-	int			 dir;
-
-	if (hint == 0)
-		return ENOMEM;
-
-	/* Calculate upper and lower bound for selected address. */
-	high = hint + uaddr->max_dist;
-	if (high < hint)	/* overflow */
-		high = map->max_offset;
-	high = MIN(high, uaddr->uaddr.uaddr_maxaddr);
-	if (high < sz)
-		return ENOMEM;	/* Protect against underflow. */
-	high -= sz;
-
-	/* Calculate lower bound for selected address. */
-	low = hint - uaddr->max_dist;
-	if (low > hint)		/* underflow */
-		low = map->min_offset;
-	low = MAX(low, uaddr->uaddr.uaddr_minaddr);
-
-	/* Search strategy setup. */
-	before_gap = PAGE_SIZE +
-	    (arc4random_uniform(UADDR_HINT_MAXGAP) & ~(vaddr_t)PAGE_MASK);
-	after_gap = PAGE_SIZE +
-	    (arc4random_uniform(UADDR_HINT_MAXGAP) & ~(vaddr_t)PAGE_MASK);
-	dir = (arc4random() & 0x01) ? 1 : -1;
-
-	/*
-	 * Try to search:
-	 * - forward,  with gap
-	 * - backward, with gap
-	 * - forward,  without gap
-	 * - backward, without gap
-	 * (Where forward is in the direction specified by dir and
-	 * backward is in the direction specified by -dir).
-	 */
-	if (uvm_addr_linsearch(map, uaddr_param,
-	    entry_out, addr_out, hint, sz, align, offset,
-	    dir, low, high, before_gap, after_gap) == 0)
-		return 0;
-	if (uvm_addr_linsearch(map, uaddr_param,
-	    entry_out, addr_out, hint, sz, align, offset,
-	    -dir, low, high, before_gap, after_gap) == 0)
-		return 0;
-
-	if (uvm_addr_linsearch(map, uaddr_param,
-	    entry_out, addr_out, hint, sz, align, offset,
-	    dir, low, high, 0, 0) == 0)
-		return 0;
-	if (uvm_addr_linsearch(map, uaddr_param,
-	    entry_out, addr_out, hint, sz, align, offset,
-	    -dir, low, high, 0, 0) == 0)
-		return 0;
-
-	return ENOMEM;
-}
-
-/*
  * Kernel allocation bootstrap logic.
  */
 const struct uvm_addr_functions uaddr_kernel_functions = {
@@ -1242,9 +1118,16 @@ uaddr_pivot_select(struct vm_map *map, struct uvm_addr_state *uaddr_p,
 	vsize_t				 before_gap, after_gap;
 	int				 err;
 
-	/* Hint must be handled by dedicated hint allocator. */
-	if (hint != 0)
-		return EINVAL;
+	/*
+	 * When we have a hint, use the rnd allocator that finds the
+	 * area that is closest to the hint, if there is such an area.
+	 */
+	if (hint != 0) {
+		if (uaddr_rnd_select(map, uaddr_p, entry_out, addr_out,
+		    sz, align, offset, prot, hint) == 0)
+			return 0;
+		return ENOMEM;
+	}
 
 	/*
 	 * Select a random pivot and a random gap sizes around the allocation.
diff --git a/sys/uvm/uvm_addr.h b/sys/uvm/uvm_addr.h
index 74a2cf456f1..f16126da847 100644
--- a/sys/uvm/uvm_addr.h
+++ b/sys/uvm/uvm_addr.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_addr.h,v 1.6 2016/09/16 01:51:40 dlg Exp $	*/
+/*	$OpenBSD: uvm_addr.h,v 1.7 2017/01/17 17:19:21 stefan Exp $	*/
 
 /*
  * Copyright (c) 2011 Ariane van der Steldt <ariane@stack.nl>
@@ -90,7 +90,6 @@ int			 uvm_addr_invoke(struct vm_map *,
 struct uvm_addr_state	*uaddr_lin_create(vaddr_t, vaddr_t);
 #endif
 struct uvm_addr_state	*uaddr_rnd_create(vaddr_t, vaddr_t);
-struct uvm_addr_state	*uaddr_hint_create(vaddr_t, vaddr_t, vsize_t);
 #ifndef SMALL_KERNEL
 struct uvm_addr_state	*uaddr_bestfit_create(vaddr_t, vaddr_t);
 struct uvm_addr_state	*uaddr_pivot_create(vaddr_t, vaddr_t);
diff --git a/sys/uvm/uvm_map.c b/sys/uvm/uvm_map.c
index 10a9ab0601a..75cefa47cfc 100644
--- a/sys/uvm/uvm_map.c
+++ b/sys/uvm/uvm_map.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map.c,v 1.226 2016/11/07 00:26:33 guenther Exp $	*/
+/*	$OpenBSD: uvm_map.c,v 1.227 2017/01/17 17:19:21 stefan Exp $	*/
 /*	$NetBSD: uvm_map.c,v 1.86 2000/11/27 08:40:03 chs Exp $	*/
 
 /*
@@ -5291,9 +5291,6 @@ uvm_map_setup_md(struct vm_map *map)
 		min = VMMAP_MIN_ADDR;
 
 #if 0	/* Cool stuff, not yet */
-	/* Hinted allocations. */
-	map->uaddr_any[1] = uaddr_hint_create(min, max, 1024 * 1024 * 1024);
-
 	/* Executable code is special. */
 	map->uaddr_exe = uaddr_rnd_create(min, I386_MAX_EXE_ADDR);
 	/* Place normal allocations beyond executable mappings. */
@@ -5323,13 +5320,6 @@ uvm_map_setup_md(struct vm_map *map)
 		min = VMMAP_MIN_ADDR;
 
 #if 0	/* Cool stuff, not yet */
-	/* Hinted allocations above 4GB */
-	map->uaddr_any[0] =
-	    uaddr_hint_create(0x100000000ULL, max, 1024 * 1024 * 1024);
-	/* Hinted allocations below 4GB */
-	map->uaddr_any[1] = uaddr_hint_create(min, 0x100000000ULL,
-	    1024 * 1024 * 1024);
-	/* Normal allocations, always above 4GB */
 	map->uaddr_any[3] = uaddr_pivot_create(MAX(min, 0x100000000ULL), max);
 #else	/* Crappy stuff, for now */
 	map->uaddr_any[0] = uaddr_rnd_create(min, max);
@@ -5356,9 +5346,6 @@ uvm_map_setup_md(struct vm_map *map)
 		min = VMMAP_MIN_ADDR;
 
 #if 0	/* Cool stuff, not yet */
-	/* Hinted allocations. */
-	map->uaddr_any[1] = uaddr_hint_create(min, max, 1024 * 1024 * 1024);
-	/* Normal allocations. */
 	map->uaddr_any[3] = uaddr_pivot_create(min, max);
 #else	/* Crappy stuff, for now */
 	map->uaddr_any[0] = uaddr_rnd_create(min, max);