Mon Feb 14 13:02:31 2022 UTC ()
drm/mm: Assert invariant of rb lookup.

Just to make sure I didn't get the sense of the lookup reversed,
which is quite likely, because I've done it probably more than once
in this code before...


(riastradh)
diff -r1.14 -r1.15 src/sys/external/bsd/drm2/dist/drm/drm_mm.c
cvs diff -r1.14 -r1.15 src/sys/external/bsd/drm2/dist/drm/drm_mm.c (expand / switch to unified diff)

--- src/sys/external/bsd/drm2/dist/drm/drm_mm.c 2021/12/19 11:51:32 1.14
+++ src/sys/external/bsd/drm2/dist/drm/drm_mm.c 2022/02/14 13:02:31 1.15
@@ -1,14 +1,14 @@ @@ -1,14 +1,14 @@
1/* $NetBSD: drm_mm.c,v 1.14 2021/12/19 11:51:32 riastradh Exp $ */ 1/* $NetBSD: drm_mm.c,v 1.15 2022/02/14 13:02:31 riastradh Exp $ */
2 2
3/************************************************************************** 3/**************************************************************************
4 * 4 *
5 * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. 5 * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA.
6 * Copyright 2016 Intel Corporation 6 * Copyright 2016 Intel Corporation
7 * All Rights Reserved. 7 * All Rights Reserved.
8 * 8 *
9 * Permission is hereby granted, free of charge, to any person obtaining a 9 * Permission is hereby granted, free of charge, to any person obtaining a
10 * copy of this software and associated documentation files (the 10 * copy of this software and associated documentation files (the
11 * "Software"), to deal in the Software without restriction, including 11 * "Software"), to deal in the Software without restriction, including
12 * without limitation the rights to use, copy, modify, merge, publish, 12 * without limitation the rights to use, copy, modify, merge, publish,
13 * distribute, sub license, and/or sell copies of the Software, and to 13 * distribute, sub license, and/or sell copies of the Software, and to
14 * permit persons to whom the Software is furnished to do so, subject to 14 * permit persons to whom the Software is furnished to do so, subject to
@@ -35,27 +35,27 @@ @@ -35,27 +35,27 @@
35 * 35 *
36 * Note that the algorithm used is quite simple and there might be substantial 36 * Note that the algorithm used is quite simple and there might be substantial
37 * performance gains if a smarter free list is implemented. Currently it is 37 * performance gains if a smarter free list is implemented. Currently it is
38 * just an unordered stack of free regions. This could easily be improved if 38 * just an unordered stack of free regions. This could easily be improved if
39 * an RB-tree is used instead. At least if we expect heavy fragmentation. 39 * an RB-tree is used instead. At least if we expect heavy fragmentation.
40 * 40 *
41 * Aligned allocations can also see improvement. 41 * Aligned allocations can also see improvement.
42 * 42 *
43 * Authors: 43 * Authors:
44 * Thomas Hellström <thomas-at-tungstengraphics-dot-com> 44 * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
45 */ 45 */
46 46
47#include <sys/cdefs.h> 47#include <sys/cdefs.h>
48__KERNEL_RCSID(0, "$NetBSD: drm_mm.c,v 1.14 2021/12/19 11:51:32 riastradh Exp $"); 48__KERNEL_RCSID(0, "$NetBSD: drm_mm.c,v 1.15 2022/02/14 13:02:31 riastradh Exp $");
49 49
50#include <linux/export.h> 50#include <linux/export.h>
51#include <linux/interval_tree_generic.h> 51#include <linux/interval_tree_generic.h>
52#include <linux/seq_file.h> 52#include <linux/seq_file.h>
53#include <linux/slab.h> 53#include <linux/slab.h>
54#include <linux/stacktrace.h> 54#include <linux/stacktrace.h>
55 55
56#include <drm/drm_mm.h> 56#include <drm/drm_mm.h>
57 57
58/** 58/**
59 * DOC: Overview 59 * DOC: Overview
60 * 60 *
61 * drm_mm provides a simple range allocator. The drivers are free to use the 61 * drm_mm provides a simple range allocator. The drivers are free to use the
@@ -391,27 +391,32 @@ static inline struct drm_mm_node *rb_hol @@ -391,27 +391,32 @@ static inline struct drm_mm_node *rb_hol
391static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb) 391static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb)
392{ 392{
393 return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr); 393 return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr);
394} 394}
395 395
396static inline u64 rb_hole_size(struct rb_node *rb) 396static inline u64 rb_hole_size(struct rb_node *rb)
397{ 397{
398 return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size; 398 return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size;
399} 399}
400 400
401static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size) 401static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
402{ 402{
403#ifdef __NetBSD__ 403#ifdef __NetBSD__
404 return rb_tree_find_node_leq(&mm->holes_size.rb_root.rbr_tree, &size); 404 struct drm_mm_node *best;
 405
 406 best = rb_tree_find_node_leq(&mm->holes_size.rb_root.rbr_tree, &size);
 407 KASSERT(best == NULL || size <= best->hole_size);
 408
 409 return best;
405#else 410#else
406 struct rb_node *rb = mm->holes_size.rb_root.rb_node; 411 struct rb_node *rb = mm->holes_size.rb_root.rb_node;
407 struct drm_mm_node *best = NULL; 412 struct drm_mm_node *best = NULL;
408 413
409 do { 414 do {
410 struct drm_mm_node *node = 415 struct drm_mm_node *node =
411 rb_entry(rb, struct drm_mm_node, rb_hole_size); 416 rb_entry(rb, struct drm_mm_node, rb_hole_size);
412 417
413 if (size <= node->hole_size) { 418 if (size <= node->hole_size) {
414 best = node; 419 best = node;
415 rb = rb->rb_right; 420 rb = rb->rb_right;
416 } else { 421 } else {
417 rb = rb->rb_left; 422 rb = rb->rb_left;