Module Name: src
Committed By: riastradh
Date: Tue Aug 13 17:54:44 UTC 2024
Modified Files:
src/sys/uvm: uvm_map.c
Log Message:
uvm_map(9): Sprinkle assertions and interface contract comments.
No functional change intended.
PR kern/51254: uvm assertion "!topdown || hint <= orig_hint" failed
To generate a diff of this commit:
cvs rdiff -u -r1.413 -r1.414 src/sys/uvm/uvm_map.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/uvm/uvm_map.c
diff -u src/sys/uvm/uvm_map.c:1.413 src/sys/uvm/uvm_map.c:1.414
--- src/sys/uvm/uvm_map.c:1.413 Tue Jul 16 16:48:54 2024
+++ src/sys/uvm/uvm_map.c Tue Aug 13 17:54:44 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: uvm_map.c,v 1.413 2024/07/16 16:48:54 uwe Exp $ */
+/* $NetBSD: uvm_map.c,v 1.414 2024/08/13 17:54:44 riastradh Exp $ */
/*
* Copyright (c) 1997 Charles D. Cranor and Washington University.
@@ -66,7 +66,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: uvm_map.c,v 1.413 2024/07/16 16:48:54 uwe Exp $");
+__KERNEL_RCSID(0, "$NetBSD: uvm_map.c,v 1.414 2024/08/13 17:54:44 riastradh Exp $");
#include "opt_ddb.h"
#include "opt_pax.h"
@@ -303,11 +303,23 @@ int _uvm_map_sanity(struct vm_map *);
int _uvm_tree_sanity(struct vm_map *);
static vsize_t uvm_rb_maxgap(const struct vm_map_entry *);
-#define ROOT_ENTRY(map) ((struct vm_map_entry *)(map)->rb_tree.rbt_root)
-#define LEFT_ENTRY(entry) ((struct vm_map_entry *)(entry)->rb_node.rb_left)
-#define RIGHT_ENTRY(entry) ((struct vm_map_entry *)(entry)->rb_node.rb_right)
-#define PARENT_ENTRY(map, entry) \
- (ROOT_ENTRY(map) == (entry) \
+/*
+ * Tree iteration. We violate the rbtree(9) abstraction for various
+ * things here. Entries are ascending left to right, so, provided the
+ * child entry in question exists:
+ *
+ * LEFT_ENTRY(entry)->end <= entry->start
+ * entry->end <= RIGHT_ENTRY(entry)->start
+ */
+__CTASSERT(offsetof(struct vm_map_entry, rb_node) == 0);
+#define ROOT_ENTRY(map) \
+ ((struct vm_map_entry *)(map)->rb_tree.rbt_root)
+#define LEFT_ENTRY(entry) \
+ ((struct vm_map_entry *)(entry)->rb_node.rb_left)
+#define RIGHT_ENTRY(entry) \
+ ((struct vm_map_entry *)(entry)->rb_node.rb_right)
+#define PARENT_ENTRY(map, entry) \
+ (ROOT_ENTRY(map) == (entry) \
? NULL : (struct vm_map_entry *)RB_FATHER(&(entry)->rb_node))
/*
@@ -1619,6 +1631,18 @@ done:
/*
* uvm_map_lookup_entry_bytree: lookup an entry in tree
+ *
+ * => map must at least be read-locked by caller.
+ *
+ * => If address lies in an entry, set *entry to it and return true;
+ * then (*entry)->start <= address < (*entry)->end.
+
+ * => If address is below all entries in map, return false and set
+ * *entry to &map->header.
+ *
+ * => Otherwise, return false and set *entry to the highest entry below
+ * address, so (*entry)->end <= address, and if (*entry)->next is
+ * not &map->header, address < (*entry)->next->start.
*/
static inline bool
@@ -1628,7 +1652,10 @@ uvm_map_lookup_entry_bytree(struct vm_ma
struct vm_map_entry *prev = &map->header;
struct vm_map_entry *cur = ROOT_ENTRY(map);
+ KASSERT(rw_lock_held(&map->lock));
+
while (cur) {
+ KASSERT(prev == &map->header || prev->end <= address);
UVMMAP_EVCNT_INCR(mlk_treeloop);
if (address >= cur->start) {
if (address < cur->end) {
@@ -1636,10 +1663,14 @@ uvm_map_lookup_entry_bytree(struct vm_ma
return true;
}
prev = cur;
+ KASSERT(prev->end <= address);
cur = RIGHT_ENTRY(cur);
+ KASSERT(prev->end <= cur->start);
} else
cur = LEFT_ENTRY(cur);
}
+ KASSERT(prev == &map->header || prev->end <= address);
+ KASSERT(prev->next == &map->header || address < prev->next->start);
*entry = prev;
return false;
}
@@ -1647,9 +1678,17 @@ uvm_map_lookup_entry_bytree(struct vm_ma
/*
* uvm_map_lookup_entry: find map entry at or before an address
*
- * => map must at least be read-locked by caller
- * => entry is returned in "entry"
- * => return value is true if address is in the returned entry
+ * => map must at least be read-locked by caller.
+ *
+ * => If address lies in an entry, set *entry to it and return true;
+ * then (*entry)->start <= address < (*entry)->end.
+
+ * => If address is below all entries in map, return false and set
+ * *entry to &map->header.
+ *
+ * => Otherwise, return false and set *entry to the highest entry below
+ * address, so (*entry)->end <= address, and if (*entry)->next is
+ * not &map->header, address < (*entry)->next->start.
*/
bool
@@ -1661,6 +1700,8 @@ uvm_map_lookup_entry(struct vm_map *map,
UVMHIST_CALLARGS(maphist,"(map=%#jx,addr=%#jx,ent=%#jx)",
(uintptr_t)map, address, (uintptr_t)entry, 0);
+ KDASSERT(rw_lock_held(&map->lock));
+
/*
* make a quick check to see if we are already looking at
* the entry we want (which is usually the case). note also
@@ -1938,18 +1979,23 @@ uvm_map_findspace(struct vm_map *map, va
* optimization or find a better way to do it.
*/
entry = map->first_free;
+ } else if (uvm_map_lookup_entry(map, hint, &entry)) {
+ KASSERT(entry->start <= hint);
+ KASSERT(hint < entry->end);
+ /* "hint" address already in use ... */
+ if (flags & UVM_FLAG_FIXED) {
+ UVMHIST_LOG(maphist, "<- fixed & VA in use",
+ 0, 0, 0, 0);
+ return (NULL);
+ }
+ if (topdown)
+ /* Start from lower gap. */
+ entry = entry->prev;
} else {
- if (uvm_map_lookup_entry(map, hint, &entry)) {
- /* "hint" address already in use ... */
- if (flags & UVM_FLAG_FIXED) {
- UVMHIST_LOG(maphist, "<- fixed & VA in use",
- 0, 0, 0, 0);
- return (NULL);
- }
- if (topdown)
- /* Start from lower gap. */
- entry = entry->prev;
- } else if (flags & UVM_FLAG_FIXED) {
+ KASSERT(entry == &map->header || entry->end <= hint);
+ KASSERT(entry->next == &map->header ||
+ hint < entry->next->start);
+ if (flags & UVM_FLAG_FIXED) {
if (entry->next->start >= hint + length &&
hint + length > hint)
goto found;
