summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDeepak Nibade <dnibade@nvidia.com>2017-03-30 05:10:09 -0400
committermobile promotions <svcmobile_promotions@nvidia.com>2017-04-06 13:57:22 -0400
commit6dda47a114d1ecbef4f5fa77e8100d795ee23ff1 (patch)
tree87c3fecc7e473dc669256fab16cbf0dba765a995
parent335b3fa2fe89de3ae37d01a8e9605dc74554f777 (diff)
gpu: nvgpu: add rbtree implementation
In order to remove nvgpu's dependency from Linux, add nvgpu's own rbtree implementation Define a rbtree node as struct nvgpu_rbtree_node *node; Add below APIs to support rbtree operations nvgpu_rbtree_insert() - insert a new node into tree nvgpu_rbtree_unlink() - remove a node from tree nvgpu_rbtree_search() - search a key in tree nvgpu_rbtree_range_search() - search a node with key falling in range nvgpu_rbtree_less_than_search() - search a node with key lesser than given key nvgpu_rbtree_enum_start() - start enumerating a tree nvgpu_rbtree_enum_next() - find next node in enumeration Jira NVGPU-13 Change-Id: Idceb375dc20d9411799c92608b0264e59886bf68 Signed-off-by: Deepak Nibade <dnibade@nvidia.com> Reviewed-on: http://git-master/r/1331537 Reviewed-by: mobile promotions <svcmobile_promotions@nvidia.com> Tested-by: mobile promotions <svcmobile_promotions@nvidia.com>
Diffstat
-rw-r--r--drivers/gpu/nvgpu/Makefile.nvgpu1
-rw-r--r--drivers/gpu/nvgpu/common/rbtree.c429
-rw-r--r--drivers/gpu/nvgpu/include/nvgpu/rbtree.h124
3 files changed, 554 insertions, 0 deletions
diff --git a/drivers/gpu/nvgpu/Makefile.nvgpu b/drivers/gpu/nvgpu/Makefile.nvgpu
index b8a3f033..16c54849 100644
--- a/drivers/gpu/nvgpu/Makefile.nvgpu
+++ b/drivers/gpu/nvgpu/Makefile.nvgpu
@@ -40,6 +40,7 @@ nvgpu-y := \
40 common/nvgpu_common.o \ 40 common/nvgpu_common.o \
41 common/semaphore.o \ 41 common/semaphore.o \
42 common/as.o \ 42 common/as.o \
43 common/rbtree.o \
43 common/vbios/bios.o \ 44 common/vbios/bios.o \
44 gk20a/gk20a.o \ 45 gk20a/gk20a.o \
45 gk20a/bus_gk20a.o \ 46 gk20a/bus_gk20a.o \
diff --git a/drivers/gpu/nvgpu/common/rbtree.c b/drivers/gpu/nvgpu/common/rbtree.c
new file mode 100644
index 00000000..0fcbe86e
--- /dev/null
+++ b/drivers/gpu/nvgpu/common/rbtree.c
@@ -0,0 +1,429 @@
1/*
2 * Copyright (c) 2017, NVIDIA CORPORATION. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms and conditions of the GNU General Public License,
6 * version 2, as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
11 * more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 */
16
17#include <nvgpu/rbtree.h>
18
19/*
20 * rotate node x to left
21 */
22static void rotate_left(struct nvgpu_rbtree_node **root,
23 struct nvgpu_rbtree_node *x)
24{
25 struct nvgpu_rbtree_node *y = x->right;
26
27 /* establish x->right link */
28 x->right = y->left;
29 if (y->left)
30 y->left->parent = x;
31
32 /* establish y->parent link */
33 y->parent = x->parent;
34 if (x->parent) {
35 if (x == x->parent->left)
36 x->parent->left = y;
37 else
38 x->parent->right = y;
39 } else {
40 *root = y;
41 }
42
43 /* link x and y */
44 y->left = x;
45 x->parent = y;
46}
47
48/*
49 * rotate node x to right
50 */
51static void rotate_right(struct nvgpu_rbtree_node **root,
52 struct nvgpu_rbtree_node *x)
53{
54 struct nvgpu_rbtree_node *y = x->left;
55
56 /* establish x->left link */
57 x->left = y->right;
58 if (y->right)
59 y->right->parent = x;
60
61 /* establish y->parent link */
62 y->parent = x->parent;
63 if (x->parent) {
64 if (x == x->parent->right)
65 x->parent->right = y;
66 else
67 x->parent->left = y;
68 } else {
69 *root = y;
70 }
71
72 /* link x and y */
73 y->right = x;
74 x->parent = y;
75}
76
77/*
78 * maintain red-black tree balance after inserting node x
79 */
80static void insert_fixup(struct nvgpu_rbtree_node **root,
81 struct nvgpu_rbtree_node *x)
82{
83 /* check red-black properties */
84 while ((x != *root) && x->parent->is_red) {
85 /* we have a violation */
86 if (x->parent == x->parent->parent->left) {
87 struct nvgpu_rbtree_node *y = x->parent->parent->right;
88
89 if (y && y->is_red) {
90 /* uncle is RED */
91 x->parent->is_red = false;
92 y->is_red = false;
93 x->parent->parent->is_red = true;
94 x = x->parent->parent;
95 } else {
96 /* uncle is BLACK */
97 if (x == x->parent->right) {
98 /* make x a left child */
99 x = x->parent;
100 rotate_left(root, x);
101 }
102
103 /* recolor and rotate */
104 x->parent->is_red = false;
105 x->parent->parent->is_red = true;
106 rotate_right(root, x->parent->parent);
107 }
108 } else {
109 /* mirror image of above code */
110 struct nvgpu_rbtree_node *y = x->parent->parent->left;
111
112 if (y && y->is_red) {
113 /* uncle is RED */
114 x->parent->is_red = false;
115 y->is_red = false;
116 x->parent->parent->is_red = true;
117 x = x->parent->parent;
118 } else {
119 /* uncle is BLACK */
120 if (x == x->parent->left) {
121 x = x->parent;
122 rotate_right(root, x);
123 }
124 x->parent->is_red = false;
125 x->parent->parent->is_red = true;
126 rotate_left(root, x->parent->parent);
127 }
128 }
129 }
130
131 (*root)->is_red = false;
132}
133
134void nvgpu_rbtree_insert(struct nvgpu_rbtree_node *new_node,
135 struct nvgpu_rbtree_node **root)
136{
137 struct nvgpu_rbtree_node *curr;
138 struct nvgpu_rbtree_node *parent;
139
140 /* find future parent */
141 curr = *root;
142 parent = NULL;
143
144 while (curr) {
145 parent = curr;
146 if (new_node->key_start < curr->key_start)
147 curr = curr->left;
148 else if (new_node->key_start > curr->key_start)
149 curr = curr->right;
150 else
151 return; /* duplicate entry */
152 }
153
154 /* the caller allocated the node already, just fix the links */
155 new_node->parent = parent;
156 new_node->left = NULL;
157 new_node->right = NULL;
158 new_node->is_red = true;
159
160 /* insert node in tree */
161 if (parent) {
162 if (new_node->key_start < parent->key_start)
163 parent->left = new_node;
164 else
165 parent->right = new_node;
166 } else {
167 *root = new_node;
168 }
169
170 insert_fixup(root, new_node);
171}
172
173/*
174 * maintain red-black tree balance after deleting node x
175 */
176static void _delete_fixup(struct nvgpu_rbtree_node **root,
177 struct nvgpu_rbtree_node *parent_of_x,
178 struct nvgpu_rbtree_node *x)
179{
180 while ((x != *root) && (!x || !x->is_red)) {
181 /*
182 * NULL nodes are sentinel nodes. If we delete a sentinel
183 * node (x==NULL) it must have a parent node (or be the root).
184 * Hence, parent_of_x == NULL with
185 * x==NULL is never possible (tree invariant)
186 */
187
188 if ((parent_of_x != NULL) && (x == parent_of_x->left)) {
189 struct nvgpu_rbtree_node *w = parent_of_x->right;
190
191 if (w && w->is_red) {
192 w->is_red = false;
193 parent_of_x->is_red = true;
194 rotate_left(root, parent_of_x);
195 w = parent_of_x->right;
196 }
197
198 if (!w || ((!w->left || !w->left->is_red)
199 && (!w->right || !w->right->is_red))) {
200 if (w)
201 w->is_red = true;
202 x = parent_of_x;
203 } else {
204 if (!w->right || !w->right->is_red) {
205 w->left->is_red = false;
206 w->is_red = true;
207 rotate_right(root, w);
208 w = parent_of_x->right;
209 }
210 w->is_red = parent_of_x->is_red;
211 parent_of_x->is_red = false;
212 w->right->is_red = false;
213 rotate_left(root, parent_of_x);
214 x = *root;
215 }
216 } else if (parent_of_x != NULL) {
217 struct nvgpu_rbtree_node *w = parent_of_x->left;
218
219 if (w && w->is_red) {
220 w->is_red = false;
221 parent_of_x->is_red = true;
222 rotate_right(root, parent_of_x);
223 w = parent_of_x->left;
224 }
225
226 if (!w || ((!w->right || !w->right->is_red)
227 && (!w->left || !w->left->is_red))) {
228 if (w)
229 w->is_red = true;
230 x = parent_of_x;
231 } else {
232 if (!w->left || !w->left->is_red) {
233 w->right->is_red = false;
234 w->is_red = true;
235 rotate_left(root, w);
236 w = parent_of_x->left;
237 }
238 w->is_red = parent_of_x->is_red;
239 parent_of_x->is_red = false;
240 w->left->is_red = false;
241 rotate_right(root, parent_of_x);
242 x = *root;
243 }
244 }
245 parent_of_x = x->parent;
246 }
247
248 if (x)
249 x->is_red = false;
250}
251
252void nvgpu_rbtree_unlink(struct nvgpu_rbtree_node *node,
253 struct nvgpu_rbtree_node **root)
254{
255 struct nvgpu_rbtree_node *x;
256 struct nvgpu_rbtree_node *y;
257 struct nvgpu_rbtree_node *z;
258 struct nvgpu_rbtree_node *parent_of_x;
259 bool y_was_black;
260
261 z = node;
262
263 /* unlink */
264 if (!z->left || !z->right) {
265 /* y has a SENTINEL node as a child */
266 y = z;
267 } else {
268 /* find tree successor */
269 y = z->right;
270 while (y->left)
271 y = y->left;
272 }
273
274 /* x is y's only child */
275 if (y->left)
276 x = y->left;
277 else
278 x = y->right;
279
280 /* remove y from the parent chain */
281 parent_of_x = y->parent;
282 if (x)
283 x->parent = parent_of_x;
284
285 if (y->parent) {
286 if (y == y->parent->left)
287 y->parent->left = x;
288 else
289 y->parent->right = x;
290 } else {
291 *root = x;
292 }
293
294 y_was_black = !y->is_red;
295 if (y != z) {
296 /* we need to replace z with y so
297 * the memory for z can be freed
298 */
299 y->parent = z->parent;
300 if (z->parent) {
301 if (z == z->parent->left)
302 z->parent->left = y;
303 else
304 z->parent->right = y;
305 } else {
306 *root = y;
307 }
308
309 y->is_red = z->is_red;
310
311 y->left = z->left;
312 if (z->left)
313 z->left->parent = y;
314
315 y->right = z->right;
316 if (z->right)
317 z->right->parent = y;
318
319 if (parent_of_x == z)
320 parent_of_x = y;
321 }
322
323 if (y_was_black)
324 _delete_fixup(root, parent_of_x, x);
325}
326
327void nvgpu_rbtree_search(u64 key_start, struct nvgpu_rbtree_node **node,
328 struct nvgpu_rbtree_node *root)
329{
330 struct nvgpu_rbtree_node *curr = root;
331
332 while (curr) {
333 if (key_start < curr->key_start) {
334 curr = curr->left;
335 } else if (key_start > curr->key_start) {
336 curr = curr->right;
337 } else {
338 *node = curr;
339 return;
340 }
341 }
342
343 *node = NULL;
344}
345
346void nvgpu_rbtree_range_search(u64 key,
347 struct nvgpu_rbtree_node **node,
348 struct nvgpu_rbtree_node *root)
349{
350 struct nvgpu_rbtree_node *curr = root;
351
352 while (curr) {
353 if (key >= curr->key_start &&
354 key < curr->key_end) {
355 *node = curr;
356 return;
357 } else if (key < curr->key_start) {
358 curr = curr->left;
359 } else {
360 curr = curr->right;
361 }
362 }
363
364 *node = NULL;
365}
366
367void nvgpu_rbtree_less_than_search(u64 key_start,
368 struct nvgpu_rbtree_node **node,
369 struct nvgpu_rbtree_node *root)
370{
371 struct nvgpu_rbtree_node *curr = root;
372
373 while (curr) {
374 if (key_start <= curr->key_start) {
375 curr = curr->left;
376 } else {
377 *node = curr;
378 curr = curr->right;
379 }
380 }
381}
382
383void nvgpu_rbtree_enum_start(u64 key_start, struct nvgpu_rbtree_node **node,
384 struct nvgpu_rbtree_node *root)
385{
386 *node = NULL;
387
388 if (root) {
389 struct nvgpu_rbtree_node *curr = root;
390
391 while (curr) {
392 if (key_start < curr->key_start) {
393 *node = curr;
394 curr = curr->left;
395 } else if (key_start > curr->key_start) {
396 curr = curr->right;
397 } else {
398 *node = curr;
399 break;
400 }
401 }
402 }
403}
404
405void nvgpu_rbtree_enum_next(struct nvgpu_rbtree_node **node,
406 struct nvgpu_rbtree_node *root)
407{
408 struct nvgpu_rbtree_node *curr = NULL;
409
410 if (root && *node) {
411 /* if we don't have a right subtree return the parent */
412 curr = *node;
413
414 /* pick the leftmost node of the right subtree ? */
415 if (curr->right) {
416 curr = curr->right;
417 for (; curr->left;)
418 curr = curr->left;
419 } else {
420 /* go up until we find the right inorder node */
421 for (curr = curr->parent; curr; curr = curr->parent) {
422 if (curr->key_start > (*node)->key_start)
423 break;
424 }
425 }
426 }
427
428 *node = curr;
429}
diff --git a/drivers/gpu/nvgpu/include/nvgpu/rbtree.h b/drivers/gpu/nvgpu/include/nvgpu/rbtree.h
new file mode 100644
index 00000000..c29957c2
--- /dev/null
+++ b/drivers/gpu/nvgpu/include/nvgpu/rbtree.h
@@ -0,0 +1,124 @@
1/*
2 * Copyright (c) 2017, NVIDIA CORPORATION. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms and conditions of the GNU General Public License,
6 * version 2, as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
11 * more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 */
16
17#ifndef __NVGPU_RBTREE_H__
18#define __NVGPU_RBTREE_H__
19
20#include <nvgpu/types.h>
21
22struct nvgpu_rbtree_node {
23 u64 key_start;
24 u64 key_end;
25
26 bool is_red; /* !IsRed == IsBlack */
27
28 struct nvgpu_rbtree_node *parent;
29 struct nvgpu_rbtree_node *left;
30 struct nvgpu_rbtree_node *right;
31};
32
33/**
34 * nvgpu_rbtree_insert - insert a new node into rbtree
35 *
36 * @new_node Pointer to new node.
37 * @root Pointer to root of tree
38 *
39 * Nodes with duplicate key_start and overlapping ranges
40 * are not allowed
41 */
42void nvgpu_rbtree_insert(struct nvgpu_rbtree_node *new_node,
43 struct nvgpu_rbtree_node **root);
44
45/**
46 * nvgpu_rbtree_unlink - delete a node from rbtree
47 *
48 * @node Pointer to node to be deleted
49 * @root Pointer to root of tree
50 */
51void nvgpu_rbtree_unlink(struct nvgpu_rbtree_node *node,
52 struct nvgpu_rbtree_node **root);
53
54/**
55 * nvgpu_rbtree_search - search a given key in rbtree
56 *
57 * @key_start Key to be searched in rbtree
58 * @node Node pointer to be returned
59 * @root Pointer to root of tree
60 *
61 * This API will match given key against key_start of each node
62 * In case of a hit, node points to a node with given key
63 * In case of a miss, node is NULL
64 */
65void nvgpu_rbtree_search(u64 key_start, struct nvgpu_rbtree_node **node,
66 struct nvgpu_rbtree_node *root);
67
68/**
69 * nvgpu_rbtree_range_search - search a node with key falling in range
70 *
71 * @key Key to be searched in rbtree
72 * @node Node pointer to be returned
73 * @root Pointer to root of tree
74 *
75 * This API will match given key and find a node where key value
76 * falls within range of {start, end} keys
77 * In case of a hit, node points to a node with given key
78 * In case of a miss, node is NULL
79 */
80void nvgpu_rbtree_range_search(u64 key,
81 struct nvgpu_rbtree_node **node,
82 struct nvgpu_rbtree_node *root);
83
84/**
85 * nvgpu_rbtree_less_than_search - search a node with key lesser than given key
86 *
87 * @key_start Key to be searched in rbtree
88 * @node Node pointer to be returned
89 * @root Pointer to root of tree
90 *
91 * This API will match given key and find a node with highest
92 * key value lesser than given key
93 * In case of a hit, node points to a node with given key
94 * In case of a miss, node is NULL
95 */
96void nvgpu_rbtree_less_than_search(u64 key_start,
97 struct nvgpu_rbtree_node **node,
98 struct nvgpu_rbtree_node *root);
99
100/**
101 * nvgpu_rbtree_enum_start - enumerate tree starting at the node with specified value
102 *
103 * @key_start Key value to begin enumeration from
104 * @node Pointer to first node in the tree
105 * @root Pointer to root of tree
106 *
107 * This API returns node pointer pointing to first node in the rbtree
108 */
109void nvgpu_rbtree_enum_start(u64 key_start,
110 struct nvgpu_rbtree_node **node,
111 struct nvgpu_rbtree_node *root);
112
113/**
114 * nvgpu_rbtree_enum_next - find next node in enumeration
115 *
116 * @node Pointer to next node in the tree
117 * @root Pointer to root of tree
118 *
119 * This API returns node pointer pointing to next node in the rbtree
120 */
121void nvgpu_rbtree_enum_next(struct nvgpu_rbtree_node **node,
122 struct nvgpu_rbtree_node *root);
123
124#endif /* __NVGPU_RBTREE_H__ */
generated by cgit v1.2.2 (git 2.25.0) at 2024-07-02 20:54:00 -0400