[RFC][PATCH] Make GetXIDRange O(1) instead of O(N^2)
Roberto Ragusa
mail at robertoragusa.it
Mon May 27 02:56:06 PDT 2013
Hi,
I would like feedback about this patch (do not consider it ready to merge!)
The GetXIDRange function in dix/resource.c can show incredibly bad performance
in some cases; it can degenerate to O(N*2) behavior and make the system
completely unusable.
(see http://lists.x.org/archives/xorg-devel/2012-November/034555.html
for a description of one manifestation of the problem)
The basic problem is that when a client (xcb?) asks for free ids, the
code makes a lot of inefficient guesses and spends an awful amount of time
in identifying range of elements NOT present in its data structures (hashes).
This patch, in addition to raising the max hash size from 2^11 to 2^16 (2^11 was
decided in 1994, or maybe even 1987), adds explicit tracking of free ids.
The data structure I've chosen is an rb-tree of free extents.
At the start, free resources are 0-0x7ffffff (one extent).
After you allocate 5 and 8, the tree contains three extents (0-4, 6-7, 9-0x7ffffff).
After you free 5, the tree contains two extents (0-7, 9-0x7ffffff).
The good part is that when GetXIDRange is invoked, we just take a range
from the tree and return that, instantly.
The patch has been running on my machine for some months with great performance
and no strange effects (there is a problem I'm investigating which could be an
unrelated kwin bug).
I need comments from experts about one strange thing I've discovered:
- clients sometime "add" resources with already used IDs; it looks like the newer
resource is returned by "get", and that all of them are deleted by "free";
is this a bug in the applications? I decided to not change the external behavior of the
code in these circumstances (see the functions containing "maybe" in their names)
As regards the practical implementation:
- the rbtree code comes from
http://en.literateprograms.org/index.php?title=Special:DownloadCode/Red-black_tree_%28C%29&oldid=18555
please check if the license is acceptable
- the rbtree code could be in different files, I've just pasted it in resource.c to avoid
makefile changes
- the code is big but there is a lot of useless stuff (tree verification, statistics, debug
facilities)
- the code runs with debug off; but if you touch /tmp/xdbg it enables debug after a few seconds,
logs everything for a few seconds, then turns it off again (removes /tmp/xdbg); this is
my way to explore how it is working on a real everyday-used system
Any comment will be really appreciated.
Thank you.
(patch is against xorg-server-1.12.4)
--- resource.c_ORIG 2012-05-17 19:09:02.000000000 +0200
+++ resource.c 2013-05-25 16:48:40.424770241 +0200
@@ -148,6 +148,672 @@
#include "Xserver-dtrace.h"
+
+
+
+static int dbg_on=0;
+#define DBG(fmt,...) do{if(dbg_on){LogMessage(X_INFO,fmt,##__VA_ARGS__);}} while(0)
+
+typedef struct XIDextent_t{
+ XID from;
+ XID to;
+} XIDextent;
+
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+ #include <sys/types.h>
+ #include <sys/stat.h>
+ #include <unistd.h>
+
+enum rbtree_node_color { RED, BLACK };
+
+typedef struct rbtree_node_t {
+ XIDextent extent;
+ struct rbtree_node_t* left;
+ struct rbtree_node_t* right;
+ struct rbtree_node_t* parent;
+ enum rbtree_node_color color;
+} *rbtree_node;
+
+typedef struct rbtree_t {
+ rbtree_node root;
+ int stat_inserts;
+ int stat_deletes;
+ int stat_lookups;
+ int stat_lookup_evals;
+ int stat_mark_used;
+ int stat_mark_used_omit;
+ int stat_mark_unused;
+ int stat_maybe_mark_unused;
+} *rbtree;
+
+typedef int (*compare_func)(XIDextent* left, XIDextent* right);
+
+static rbtree rbtree_create();
+static XIDextent* rbtree_lookup(rbtree t, XIDextent* extent, compare_func compare);
+static void rbtree_insert(rbtree t, XIDextent* extent, compare_func compare);
+static void rbtree_delete(rbtree t, XIDextent* extent, compare_func compare);
+
+
+typedef rbtree_node node;
+typedef enum rbtree_node_color color;
+
+static node grandparent(node n);
+static node sibling(node n);
+static node uncle(node n);
+static void verify_properties(rbtree t);
+static void verify_property_1(node root);
+static void verify_property_2(node root);
+static color node_color(node n);
+static void verify_property_4(node root);
+static void verify_property_5(node root);
+static void verify_property_5_helper(node n, int black_count, int* black_count_path);
+
+static node new_node(XIDextent* extent, color node_color, node left, node right);
+static node lookup_node(rbtree t, XIDextent* extent, compare_func compare);
+static void rotate_left(rbtree t, node n);
+static void rotate_right(rbtree t, node n);
+
+static void replace_node(rbtree t, node oldn, node newn);
+static void insert_case1(rbtree t, node n);
+static void insert_case2(rbtree t, node n);
+static void insert_case3(rbtree t, node n);
+static void insert_case4(rbtree t, node n);
+static void insert_case5(rbtree t, node n);
+static node minimum_node(node root);
+static node maximum_node(node root);
+static void delete_case1(rbtree t, node n);
+static void delete_case2(rbtree t, node n);
+static void delete_case3(rbtree t, node n);
+static void delete_case4(rbtree t, node n);
+static void delete_case5(rbtree t, node n);
+static void delete_case6(rbtree t, node n);
+
+static node grandparent(node n) {
+ assert (n != NULL);
+ assert (n->parent != NULL); /* Not the root node */
+ assert (n->parent->parent != NULL); /* Not child of root */
+ return n->parent->parent;
+}
+static node sibling(node n) {
+ assert (n != NULL);
+ assert (n->parent != NULL); /* Root node has no sibling */
+ if (n == n->parent->left)
+ return n->parent->right;
+ else
+ return n->parent->left;
+}
+static node uncle(node n) {
+ assert (n != NULL);
+ assert (n->parent != NULL); /* Root node has no uncle */
+ assert (n->parent->parent != NULL); /* Children of root have no uncle */
+ return sibling(n->parent);
+}
+static void verify_properties(rbtree t) {
+#define VERIFY_RBTREEnot
+#ifdef VERIFY_RBTREE
+ verify_property_1(t->root);
+ verify_property_2(t->root);
+ /* Property 3 is implicit */
+ verify_property_4(t->root);
+ verify_property_5(t->root);
+ DBG("rbtree verified\n");
+#endif
+}
+static void verify_property_1(node n) {
+ assert(node_color(n) == RED || node_color(n) == BLACK);
+ if (n == NULL) return;
+ verify_property_1(n->left);
+ verify_property_1(n->right);
+}
+static void verify_property_2(node root) {
+ assert(node_color(root) == BLACK);
+}
+static color node_color(node n) {
+ return n == NULL ? BLACK : n->color;
+}
+static void verify_property_4(node n) {
+ if (node_color(n) == RED) {
+ assert (node_color(n->left) == BLACK);
+ assert (node_color(n->right) == BLACK);
+ assert (node_color(n->parent) == BLACK);
+ }
+ if (n == NULL) return;
+ verify_property_4(n->left);
+ verify_property_4(n->right);
+}
+static void verify_property_5(node root) {
+ int black_count_path = -1;
+ verify_property_5_helper(root, 0, &black_count_path);
+}
+
+static void verify_property_5_helper(node n, int black_count, int* path_black_count) {
+ if (node_color(n) == BLACK) {
+ black_count++;
+ }
+ if (n == NULL) {
+ if (*path_black_count == -1) {
+ *path_black_count = black_count;
+ } else {
+ assert (black_count == *path_black_count);
+ }
+ return;
+ }
+ verify_property_5_helper(n->left, black_count, path_black_count);
+ verify_property_5_helper(n->right, black_count, path_black_count);
+}
+static rbtree rbtree_create() {
+ rbtree t = malloc(sizeof(struct rbtree_t));
+ if (t==NULL)
+ return NULL;
+ t->root = NULL;
+ t->stat_inserts=0;
+ t->stat_deletes=0;
+ t->stat_lookups=0;
+ t->stat_lookup_evals=0;
+ t->stat_mark_used=0;
+ t->stat_mark_used_omit=0;
+ t->stat_mark_unused=0;
+ t->stat_maybe_mark_unused=0;
+ verify_properties(t);
+ return t;
+}
+static void recursively_destroy_node(node n) {
+ if (n->left)
+ recursively_destroy_node(n->left);
+ if (n->right)
+ recursively_destroy_node(n->right);
+ free(n);
+}
+static void rbtree_destroy(rbtree t) {
+ node n=t->root;
+ recursively_destroy_node(n);
+ free(t);
+}
+static node new_node(XIDextent* extent, color node_color, node left, node right) {
+ node result = malloc(sizeof(struct rbtree_node_t));
+ if (result==NULL)
+ return NULL;
+ result->extent.from = extent->from;
+ result->extent.to = extent->to;
+ result->color = node_color;
+ result->left = left;
+ result->right = right;
+ if (left != NULL) left->parent = result;
+ if (right != NULL) right->parent = result;
+ result->parent = NULL;
+ return result;
+}
+static node lookup_node(rbtree t, XIDextent* extent, compare_func compare) {
+ node n = t->root;
+ while (n != NULL) {
+ int comp_result = compare(extent, &n->extent);
+ t->stat_lookup_evals++;
+ if (comp_result == 0) {
+ return n;
+ } else if (comp_result < 0) {
+ n = n->left;
+ } else {
+ assert(comp_result > 0);
+ n = n->right;
+ }
+ }
+ return n;
+}
+ static int compare_extent_overlap(XIDextent* p1, XIDextent* p2);
+
+static XIDextent* rbtree_lookup(rbtree t, XIDextent* extent, compare_func compare) {
+ node n;
+ t->stat_lookups++;
+ DBG("looking up=%08x:%08x (%s)\n",extent->from,extent->to,compare==compare_extent_overlap?"over":"exact");
+ n = lookup_node(t, extent, compare);
+ return n == NULL ? NULL : &n->extent;
+}
+static XIDextent* rbtree_findfirst(rbtree t) {
+ node n = t->root;
+ if (n == NULL)
+ return NULL;
+ n=minimum_node(n);
+ return &n->extent;
+}
+static void rotate_left(rbtree t, node n) {
+ node r = n->right;
+ replace_node(t, n, r);
+ n->right = r->left;
+ if (r->left != NULL) {
+ r->left->parent = n;
+ }
+ r->left = n;
+ n->parent = r;
+}
+
+static void rotate_right(rbtree t, node n) {
+ node L = n->left;
+ replace_node(t, n, L);
+ n->left = L->right;
+ if (L->right != NULL) {
+ L->right->parent = n;
+ }
+ L->right = n;
+ n->parent = L;
+}
+static void replace_node(rbtree t, node oldn, node newn) {
+ if (oldn->parent == NULL) {
+ t->root = newn;
+ } else {
+ if (oldn == oldn->parent->left)
+ oldn->parent->left = newn;
+ else
+ oldn->parent->right = newn;
+ }
+ if (newn != NULL) {
+ newn->parent = oldn->parent;
+ }
+}
+ static void print_tree(rbtree t);
+static void rbtree_insert(rbtree t, XIDextent* extent, compare_func compare) {
+ t->stat_inserts++;
+ node inserted_node = new_node(extent, RED, NULL, NULL);
+ if (t->root == NULL) {
+ t->root = inserted_node;
+ } else {
+ node n = t->root;
+ while (1) {
+ int comp_result = compare(extent, &n->extent);
+ if (comp_result == 0) {
+ n->extent.from = extent->from;
+ n->extent.to = extent->to;
+ /* inserted_node isn't going to be used, don't leak it */
+ free (inserted_node);
+ return;
+ } else if (comp_result < 0) {
+ if (n->left == NULL) {
+ n->left = inserted_node;
+ break;
+ } else {
+ n = n->left;
+ }
+ } else {
+ assert (comp_result > 0);
+ if (n->right == NULL) {
+ n->right = inserted_node;
+ break;
+ } else {
+ n = n->right;
+ }
+ }
+ }
+ inserted_node->parent = n;
+ }
+ insert_case1(t, inserted_node);
+ verify_properties(t);
+ if(random()%0xff==0){
+ if(dbg_on==1){
+ print_tree(t);
+ DBG("debug deactivated\n");
+ dbg_on=0;
+ }
+ if(dbg_on==0){
+ struct stat statbuf;
+ if(stat("/tmp/xdbg",&statbuf)==0){
+ unlink("/tmp/xdbg");
+ dbg_on=1;
+ DBG("debug activated\n");
+ }
+ }
+ }
+}
+static void insert_case1(rbtree t, node n) {
+ if (n->parent == NULL)
+ n->color = BLACK;
+ else
+ insert_case2(t, n);
+}
+static void insert_case2(rbtree t, node n) {
+ if (node_color(n->parent) == BLACK)
+ return; /* Tree is still valid */
+ else
+ insert_case3(t, n);
+}
+static void insert_case3(rbtree t, node n) {
+ if (node_color(uncle(n)) == RED) {
+ n->parent->color = BLACK;
+ uncle(n)->color = BLACK;
+ grandparent(n)->color = RED;
+ insert_case1(t, grandparent(n));
+ } else {
+ insert_case4(t, n);
+ }
+}
+static void insert_case4(rbtree t, node n) {
+ if (n == n->parent->right && n->parent == grandparent(n)->left) {
+ rotate_left(t, n->parent);
+ n = n->left;
+ } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
+ rotate_right(t, n->parent);
+ n = n->right;
+ }
+ insert_case5(t, n);
+}
+static void insert_case5(rbtree t, node n) {
+ n->parent->color = BLACK;
+ grandparent(n)->color = RED;
+ if (n == n->parent->left && n->parent == grandparent(n)->left) {
+ rotate_right(t, grandparent(n));
+ } else {
+ assert (n == n->parent->right && n->parent == grandparent(n)->right);
+ rotate_left(t, grandparent(n));
+ }
+}
+static void rbtree_delete(rbtree t, XIDextent* extent, compare_func compare) {
+ node child;
+ t->stat_deletes++;
+ node n = lookup_node(t, extent, compare);
+ if (n == NULL) return; /* Key not found, do nothing */
+ if (n->left != NULL && n->right != NULL) {
+ /* Copy key/value from predecessor and then delete it instead */
+ node pred = maximum_node(n->left);
+ n->extent.from = pred->extent.from;
+ n->extent.to = pred->extent.to;
+ n = pred;
+ }
+
+ assert(n->left == NULL || n->right == NULL);
+ child = n->right == NULL ? n->left : n->right;
+ if (node_color(n) == BLACK) {
+ n->color = node_color(child);
+ delete_case1(t, n);
+ }
+ replace_node(t, n, child);
+ if (n->parent == NULL && child != NULL)
+ child->color = BLACK;
+ free(n);
+
+ verify_properties(t);
+}
+static node minimum_node(node n) {
+ assert (n != NULL);
+ while (n->left != NULL) {
+ n = n->left;
+ }
+ return n;
+}
+static node maximum_node(node n) {
+ assert (n != NULL);
+ while (n->right != NULL) {
+ n = n->right;
+ }
+ return n;
+}
+static void delete_case1(rbtree t, node n) {
+ if (n->parent == NULL)
+ return;
+ else
+ delete_case2(t, n);
+}
+static void delete_case2(rbtree t, node n) {
+ if (node_color(sibling(n)) == RED) {
+ n->parent->color = RED;
+ sibling(n)->color = BLACK;
+ if (n == n->parent->left)
+ rotate_left(t, n->parent);
+ else
+ rotate_right(t, n->parent);
+ }
+ delete_case3(t, n);
+}
+static void delete_case3(rbtree t, node n) {
+ if (node_color(n->parent) == BLACK &&
+ node_color(sibling(n)) == BLACK &&
+ node_color(sibling(n)->left) == BLACK &&
+ node_color(sibling(n)->right) == BLACK)
+ {
+ sibling(n)->color = RED;
+ delete_case1(t, n->parent);
+ }
+ else
+ delete_case4(t, n);
+}
+static void delete_case4(rbtree t, node n) {
+ if (node_color(n->parent) == RED &&
+ node_color(sibling(n)) == BLACK &&
+ node_color(sibling(n)->left) == BLACK &&
+ node_color(sibling(n)->right) == BLACK)
+ {
+ sibling(n)->color = RED;
+ n->parent->color = BLACK;
+ }
+ else
+ delete_case5(t, n);
+}
+static void delete_case5(rbtree t, node n) {
+ if (n == n->parent->left &&
+ node_color(sibling(n)) == BLACK &&
+ node_color(sibling(n)->left) == RED &&
+ node_color(sibling(n)->right) == BLACK)
+ {
+ sibling(n)->color = RED;
+ sibling(n)->left->color = BLACK;
+ rotate_right(t, sibling(n));
+ }
+ else if (n == n->parent->right &&
+ node_color(sibling(n)) == BLACK &&
+ node_color(sibling(n)->right) == RED &&
+ node_color(sibling(n)->left) == BLACK)
+ {
+ sibling(n)->color = RED;
+ sibling(n)->right->color = BLACK;
+ rotate_left(t, sibling(n));
+ }
+ delete_case6(t, n);
+}
+static void delete_case6(rbtree t, node n) {
+ sibling(n)->color = node_color(n->parent);
+ n->parent->color = BLACK;
+ if (n == n->parent->left) {
+ assert (node_color(sibling(n)->right) == RED);
+ sibling(n)->right->color = BLACK;
+ rotate_left(t, n->parent);
+ }
+ else
+ {
+ assert (node_color(sibling(n)->left) == RED);
+ sibling(n)->left->color = BLACK;
+ rotate_right(t, n->parent);
+ }
+}
+
+
+
+
+static int compare_extent_exactly(XIDextent* p1, XIDextent* p2);
+static int compare_extent_overlap(XIDextent* p1, XIDextent* p2);
+static void print_tree(rbtree t);
+static int print_tree_helper(rbtree_node n, int indent);
+
+static int compare_extent_exactly(XIDextent* p1, XIDextent* p2) { /* only matches if identical range */
+ if (p1->from < p2->from)
+ return -1;
+ if (p1->from > p2->from)
+ return 1;
+ if (p1->to < p2->to)
+ return -1;
+ if (p1->to > p2->to)
+ return 1;
+ return 0;
+}
+
+static int compare_extent_overlap(XIDextent* p1, XIDextent* p2) { /* matches if one range overlaps the other */
+ if (p1->to < p2->from)
+ return -1;
+ if (p1->from > p2->to)
+ return 1;
+ return 0;
+}
+
+#define INDENT_STEP 4
+
+static int print_tree_helper(rbtree_node n, int indent);
+
+static void print_tree(rbtree t) {
+ int cnt=print_tree_helper(t->root, 0);
+ DBG(" node count:%d\n",cnt);
+ DBG(" inserts:%d\n",t->stat_inserts);
+ DBG(" deletes:%d\n",t->stat_deletes);
+ DBG(" lookups:%d\n",t->stat_lookups);
+ DBG("lookup_evals:%d\n",t->stat_lookup_evals);
+ DBG(" mark_used:%d\n",t->stat_mark_used);
+ DBG(" mark_used_omit:%d\n",t->stat_mark_used_omit);
+ DBG(" mark_unused:%d\n",t->stat_mark_unused);
+ DBG("maybe_mark_unused:%d\n",t->stat_maybe_mark_unused);
+}
+
+static int print_tree_helper(rbtree_node n, int indent) {
+ int i;
+ char *indent_string=" ";
+ char *is;
+ int node_count=0;
+
+ if (n == NULL) {
+ DBG("<empty tree>\n");
+ return 0;
+ }
+ if (n->right != NULL) {
+ node_count+=print_tree_helper(n->right, indent + INDENT_STEP);
+ }
+ is=indent_string+100-(indent<100?indent:100);
+ for(i=0; i<indent; i++)
+ fputs(" ", stdout);
+ if (n->color == BLACK)
+ DBG("%s%08x:%08x\n", is, n->extent.from, n->extent.to);
+ else
+ DBG("%s<%08x:%08x>\n", is, n->extent.from, n->extent.to);
+ node_count++;
+ if (n->left != NULL) {
+ node_count+=print_tree_helper(n->left, indent + INDENT_STEP);
+ }
+ return node_count;
+}
+
+static void mark_id_as_unused(rbtree tree, XID id){
+ XIDextent ex;
+ XIDextent *minus1, *plus1;
+
+ tree->stat_mark_unused++;
+ DBG("marking as unused=%08x\n",id);
+ if (id>0) {
+ ex.from=id-1;
+ ex.to=id-1;
+ minus1=rbtree_lookup(tree, &ex, compare_extent_overlap);
+ }
+ else
+ minus1=NULL;
+
+ if (id<(XID)(0x7fffffff)) {
+ ex.from=id+1;
+ ex.to=id+1;
+ plus1=rbtree_lookup(tree, &ex, compare_extent_overlap);
+ }
+ else
+ plus1=NULL;
+
+ if (minus1==NULL) {
+ if (plus1==NULL) { /* new isolated extent */
+ DBG("!m1 !p1 ins %08x\n",id);
+ ex.from=id;
+ ex.to=id;
+ rbtree_insert(tree, &ex, compare_extent_exactly);
+ }
+ else { /* join id into extent [id+1,x] */
+ DBG("!m1 p1 fr %08x\n",id);
+ plus1->from=id;
+ }
+ }
+ else {
+ if (plus1==NULL) { /* join id into extent [x,id-1] */
+ DBG("m1 !p1 to %08x\n",id);
+ minus1->to=id;
+ }
+ else { /* filling a hole! merge everything into lower one and delete the higher one */
+ DBG("m1 p1\n");
+ DBG("-m1 %08x:%08x\n",minus1->from,minus1->to);
+ DBG("-p1 %08x:%08x\n",plus1->from,plus1->to);
+ minus1->to=plus1->to;
+ ex.from=plus1->from;
+ ex.to=plus1->to;
+ DBG("+m1 %08x:%08x\n",minus1->from,minus1->to);
+ DBG("+p1 %08x:%08x\n",plus1->from,plus1->to);
+ DBG("del %08x:%08x\n",ex.from,ex.to);
+ rbtree_delete(tree, &ex, compare_extent_exactly);
+ }
+ }
+}
+
+static void mark_id_as_used(rbtree tree, XID id){
+ XIDextent ex;
+ XIDextent *overlapping;
+
+ tree->stat_mark_used++;
+ DBG("marking as used=%08x\n",id);
+ ex.from=id;
+ ex.to=id;
+if(id==0x141 || (id&0xff)==0){
+ DBG("before searching\n");
+ print_tree(tree);
+}
+ overlapping=rbtree_lookup(tree, &ex, compare_extent_overlap);
+
+ if (overlapping==NULL) { /* this id is being used multiple times */
+ DBG("not actually marked, it is alreasy marked=%08x\n",id);
+ tree->stat_mark_used--;
+ tree->stat_mark_used_omit++;
+ return;
+ }
+ if (overlapping->from==id){
+ if (overlapping->to==id){ /* removing a isolated id */
+ ex.from=id;
+ ex.to=id;
+ rbtree_delete(tree, &ex, compare_extent_exactly);
+ }
+ else { /* removing first id in extent */
+ overlapping->from=id+1;
+ }
+ }
+ else {
+ if (overlapping->to==id){ /* removing last id in extent */
+ overlapping->to=id-1;
+ }
+ else { /* creating a hole, put lower part in existing node and add higher part*/
+ ex.from=id+1;
+ ex.to=overlapping->to;
+ overlapping->to=id-1;
+ rbtree_insert(tree, &ex, compare_extent_exactly);
+ }
+ }
+}
+
+static void find_unused_range(rbtree tree, XID min, XID max, XID *minp, XID *maxp){
+ XIDextent ex;
+ XIDextent* unused;
+
+ DBG("find min=%08x max=%08x\n",min,max);
+ ex.from=min;
+ ex.to=max;
+ unused=rbtree_lookup(tree, &ex, compare_extent_overlap);
+ if (unused==NULL) {
+ DBG("find returned NULL\n");
+ *minp=*maxp=0;
+ }
+ else { /* return intersection between asked and found */
+ *minp= unused->from<min ? min: unused->from;
+ *maxp= unused->to>max ? max : unused->to;
+ DBG("find returned %08x:%08x\n",*minp,*maxp);
+ }
+}
+
#define TypeNameString(t) LookupResourceName(t)
#endif
@@ -158,7 +824,7 @@
#define INITBUCKETS 64
#define INITHASHSIZE 6
-#define MAXHASHSIZE 11
+#define MAXHASHSIZE 16
typedef struct _Resource {
struct _Resource *next;
@@ -172,6 +838,7 @@
int elements;
int buckets;
int hashsize; /* log(2)(buckets) */
+ rbtree free_extents;
XID fakeID;
XID endFakeID;
} ClientResourceRec;
@@ -294,6 +961,7 @@
InitClientResources(ClientPtr client)
{
int i, j;
+ XIDextent ex;
if (client == serverClient) {
lastResourceType = RT_LASTPREDEF;
@@ -323,6 +991,16 @@
for (j = 0; j < INITBUCKETS; j++) {
clientTable[i].resources[j] = NULL;
}
+ DBG("init tree 1\n");
+ clientTable[i].free_extents=rbtree_create();
+ if (!clientTable[i].free_extents) {
+ return FALSE;
+ }
+ ex.from=0;
+ ex.to=(XID)(0x7fffffff);
+ rbtree_insert(clientTable[i].free_extents, &ex, compare_extent_exactly);
+ DBG("init tree 2\n");
+ print_tree(clientTable[i].free_extents);
return TRUE;
}
@@ -332,17 +1010,27 @@
id &= RESOURCE_ID_MASK;
switch (clientTable[client].hashsize) {
case 6:
- return ((int) (0x03F & (id ^ (id >> 6) ^ (id >> 12))));
+ return ((int) (0x003F & (id ^ (id >> 6) ^ (id >> 12))));
case 7:
- return ((int) (0x07F & (id ^ (id >> 7) ^ (id >> 13))));
+ return ((int) (0x007F & (id ^ (id >> 7) ^ (id >> 13))));
case 8:
- return ((int) (0x0FF & (id ^ (id >> 8) ^ (id >> 16))));
+ return ((int) (0x00FF & (id ^ (id >> 8) ^ (id >> 16))));
case 9:
- return ((int) (0x1FF & (id ^ (id >> 9))));
+ return ((int) (0x01FF & (id ^ (id >> 9))));
case 10:
- return ((int) (0x3FF & (id ^ (id >> 10))));
+ return ((int) (0x03FF & (id ^ (id >> 10))));
case 11:
- return ((int) (0x7FF & (id ^ (id >> 11))));
+ return ((int) (0x07FF & (id ^ (id >> 11))));
+ case 12:
+ return ((int) (0x0FFF & (id ^ (id >> 12))));
+ case 13:
+ return ((int) (0x1FFF & (id ^ (id >> 13))));
+ case 14:
+ return ((int) (0x3FFF & (id ^ (id >> 14))));
+ case 15:
+ return ((int) (0x7FFF & (id ^ (id >> 15))));
+ case 16:
+ return ((int) (0xFFFF & (id ^ (id >> 16))));
}
return -1;
}
@@ -368,33 +1056,13 @@
GetXIDRange(int client, Bool server, XID *minp, XID *maxp)
{
XID id, maxid;
- ResourcePtr *resp;
- ResourcePtr res;
- int i;
- XID goodid;
id = (Mask) client << CLIENTOFFSET;
if (server)
id |= client ? SERVER_BIT : SERVER_MINID;
maxid = id | RESOURCE_ID_MASK;
- goodid = 0;
- for (resp = clientTable[client].resources, i = clientTable[client].buckets;
- --i >= 0;) {
- for (res = *resp++; res; res = res->next) {
- if ((res->id < id) || (res->id > maxid))
- continue;
- if (((res->id - id) >= (maxid - res->id)) ?
- (goodid = AvailableID(client, id, res->id - 1, goodid)) :
- !(goodid = AvailableID(client, res->id + 1, maxid, goodid)))
- maxid = res->id - 1;
- else
- id = res->id + 1;
- }
- }
- if (id > maxid)
- id = maxid = 0;
- *minp = id;
- *maxp = maxid;
+
+ find_unused_range(clientTable[client].free_extents, id, maxid, minp, maxp);
}
/**
@@ -468,11 +1136,12 @@
int client;
ClientResourceRec *rrec;
ResourcePtr res, *head;
-
+
+ client = CLIENT_ID(id);
+ DBG("[dix] AddResource(%lx, %x, %lx), client=%d \n", (unsigned long)id, type, (unsigned long)value, client);
#ifdef XSERVER_DTRACE
XSERVER_RESOURCE_ALLOC(id, type, value, TypeNameString(type));
#endif
- client = CLIENT_ID(id);
rrec = &clientTable[client];
if (!rrec->buckets) {
ErrorF("[dix] AddResource(%lx, %x, %lx), client=%d \n",
@@ -493,6 +1162,7 @@
res->value = value;
*head = res;
rrec->elements++;
+ mark_id_as_used(rrec->free_extents, id);
CallResourceStateCallback(ResourceStateAdding, res);
return TRUE;
}
@@ -524,6 +1194,7 @@
*tptr = rptr;
}
clientTable[client].hashsize++;
+ DBG("new table size:%d\n",clientTable[client].hashsize);
for (j = clientTable[client].buckets,
rptr = clientTable[client].resources; --j >= 0; rptr++) {
for (res = *rptr; res; res = next) {
@@ -540,6 +1211,24 @@
clientTable[client].resources = resources;
}
+static void maybe_mark_id_as_unused(ClientResourceRec *rrec, int client, XID id){
+ ResourcePtr res;
+ rbtree tree;
+ DBG("maybe_mark_unused %08x\n",id);
+ res = rrec->resources[Hash(client, id)];
+ tree = rrec->free_extents;
+ tree->stat_maybe_mark_unused++;
+ while (res && (res->id != id))
+ res = res->next;
+ if (res==NULL) {
+ DBG("maybe_mark_unused: yes %08x\n",id);
+ mark_id_as_unused(tree, id);
+ }
+ else {
+ DBG("maybe_mark_unused: NO %08x\n",id);
+ }
+}
+
static void
doFreeResource(ResourcePtr res, Bool skip)
{
@@ -569,6 +1258,7 @@
if (res->id == id) {
RESTYPE rtype = res->type;
+ DBG("[dix] FreeResource1(%lx, %x, %lx), client=%d\n", (unsigned long)res->id, res->type, (unsigned long)res->value, cid);
#ifdef XSERVER_DTRACE
XSERVER_RESOURCE_FREE(res->id, res->type,
res->value, TypeNameString(res->type));
@@ -580,6 +1270,7 @@
if (*eltptr != elements)
prev = head; /* prev may no longer be valid */
+ maybe_mark_id_as_unused(&clientTable[cid], cid, id);
}
else
prev = &res->next;
@@ -600,6 +1291,7 @@
prev = head;
while ((res = *prev)) {
if (res->id == id && res->type == type) {
+ DBG("[dix] FreeResource2(%lx, %x, %lx), client=%d\n", (unsigned long)res->id, res->type, (unsigned long)res->value, cid);
#ifdef XSERVER_DTRACE
XSERVER_RESOURCE_FREE(res->id, res->type,
res->value, TypeNameString(res->type));
@@ -608,6 +1300,7 @@
clientTable[cid].elements--;
doFreeResource(res, skipFree);
+ maybe_mark_id_as_unused(&clientTable[cid], cid, id);
break;
}
@@ -746,6 +1439,8 @@
RESTYPE rtype = this->type;
if (rtype & RC_NEVERRETAIN) {
+ XID id=this->id;
+ DBG("[dix] FreeResource3(%lx, %x, %lx), client=%d\n", (unsigned long)this->id, this->type, (unsigned long)this->value, client->index);
#ifdef XSERVER_DTRACE
XSERVER_RESOURCE_FREE(this->id, this->type,
this->value, TypeNameString(this->type));
@@ -758,6 +1453,7 @@
if (*eltptr != elements)
prev = &resources[j]; /* prev may no longer be valid */
+ maybe_mark_id_as_unused(&clientTable[client->index], client->index, id);
}
else
prev = &this->next;
@@ -796,6 +1492,8 @@
head = &resources[j];
for (this = *head; this; this = *head) {
+ XID id=this->id;
+ DBG("[dix] FreeResource4(%lx, %x, %lx), client=%d\n", (unsigned long)this->id, this->type, (unsigned long)this->value, client->index);
#ifdef XSERVER_DTRACE
XSERVER_RESOURCE_FREE(this->id, this->type,
this->value, TypeNameString(this->type));
@@ -804,11 +1502,14 @@
clientTable[client->index].elements--;
doFreeResource(this, FALSE);
+ maybe_mark_id_as_unused(&clientTable[client->index], client->index, id);
}
}
free(clientTable[client->index].resources);
clientTable[client->index].resources = NULL;
clientTable[client->index].buckets = 0;
+ rbtree_destroy(clientTable[client->index].free_extents);
+ clientTable[client->index].free_extents = 0;
}
void
--
Roberto Ragusa mail at robertoragusa.it
More information about the xorg-devel
mailing list