--- xnu/xnu-8019.41.5/libkern/c++/priority_queue.cpp
+++ xnu/xnu-10002.41.9/libkern/c++/priority_queue.cpp
@@ -29,9 +29,7 @@
 #if KERNEL
 #include <kern/priority_queue.h>
 #include <mach/vm_param.h>
-#if CONFIG_KERNEL_TBI && KASAN_TBI
-#include <san/kasan.h>
-#endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
+#include <vm/vm_memtag.h>
 
 #ifdef __LP64__
 static_assert(PRIORITY_QUEUE_ENTRY_CHILD_BITS >= VM_KERNEL_POINTER_SIGNIFICANT_BITS,
@@ -131,18 +129,18 @@
 	static inline void
 	pack_child(entry_t e, const entry_t child)
 	{
-#if CONFIG_KERNEL_TBI && KASAN_TBI
-		e->tag = kasan_tbi_get_tag((long)child);
-#endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
+#if CONFIG_KERNEL_TAGGING
+		e->tag = vm_memtag_extract_tag((vm_offset_t)child);
+#endif /* CONFIG_KERNEL_TAGGING */
 		e->child = (long)child;
 	}
 
 	static inline entry_t
 	unpack_child(entry_t e)
 	{
-#if CONFIG_KERNEL_TBI && KASAN_TBI
-		return (entry_t)(kasan_tbi_tag_ptr(e->child, e->tag));
-#endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
+#if CONFIG_KERNEL_TAGGING
+		return (entry_t)(vm_memtag_add_ptr_tag(e->child, e->tag));
+#endif /* CONFIG_KERNEL_TAGGING */
 		return (entry_t)e->child;
 	}
 
@@ -236,6 +234,12 @@
 	}
 
 	static inline void
+	list_clear(entry_t e)
+	{
+		e->next = e->prev = NULL;
+	}
+
+	static inline void
 	list_remove(entry_t elt)
 	{
 		assert(elt->prev != NULL);
@@ -251,13 +255,31 @@
 		if (elt->next != NULL) {
 			elt->next->prev = elt->prev;
 		}
+		list_clear(elt);
 	}
 
 	static inline bool
 	sift_down(queue_t que, entry_t elt)
 	{
-		bool was_root = remove(que, elt);
-		insert(que, elt);
+		bool was_root = (que->pq_root == elt);
+
+		if (!was_root) {
+			remove_non_root(que, elt);
+			insert(que, elt, false);
+		} else if (unpack_child(elt)) {
+			remove_root(que, elt);
+			insert(que, elt, false);
+		} else {
+			/*
+			 * If the queue is reduced to a single element,
+			 * we have nothing to do.
+			 *
+			 * It is important not to, so that pq_root remains
+			 * non null at all times during priority changes,
+			 * so that unsynchronized peeking at the "emptiness"
+			 * of the priority queue works as expected.
+			 */
+		}
 		return was_root;
 	}
 
@@ -271,7 +293,7 @@
 		/* Remove the element from its current level list */
 		list_remove(elt);
 		/* Re-insert the element into the heap with a merge */
-		return insert(que, elt);
+		return insert(que, elt, false);
 	}
 
 	static inline entry_t
@@ -291,6 +313,7 @@
 			child = meld_pair(que, child);
 			new_root = merge_pair(que, que->pq_root, child);
 			que->pq_root = new_root;
+			pack_child(elt, nullptr);
 		}
 
 		return elt;
@@ -329,8 +352,12 @@
 	}
 
 	static inline bool
-	insert(queue_t que, entry_t elt)
-	{
+	insert(queue_t que, entry_t elt, bool clear = true)
+	{
+		if (clear) {
+			list_clear(elt);
+			pack_child(elt, nullptr);
+		}
 		return (que->pq_root = merge_pair(que, que->pq_root, elt)) == elt;
 	}
 
@@ -338,7 +365,13 @@
 	remove_root(queue_t que, entry_t old_root)
 	{
 		entry_t new_root = unpack_child(old_root);
-		que->pq_root = new_root ? meld_pair(que, new_root) : NULL;
+
+		if (new_root) {
+			que->pq_root = meld_pair(que, new_root);
+			pack_child(old_root, nullptr);
+		} else {
+			que->pq_root = NULL;
+		}
 		return old_root;
 	}
 
@@ -347,19 +380,9 @@
 	{
 		if (elt == que->pq_root) {
 			remove_root(que, elt);
-			elt->next = elt->prev = NULL;
-			elt->child = 0;
-#if CONFIG_KERNEL_TBI && KASAN_TBI
-			elt->tag = 0;
-#endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
 			return true;
 		} else {
 			remove_non_root(que, elt);
-			elt->next = elt->prev = NULL;
-			elt->child = 0;
-#if CONFIG_KERNEL_TBI && KASAN_TBI
-			elt->tag = 0;
-#endif
 			return false;
 		}
 	}