[RFC][PATCH] Make GetXIDRange O(1) instead of O(N^2)
Jamey Sharp
jamey at minilop.net
Mon May 27 21:35:25 PDT 2013
I can't give this a full review, but off-hand it seems like a good idea
to me!
Changing the max hash size should probably be a separate commit with a
commit message justifying it.
There's some precedent for putting common data structures in shared code
in xserver, notably include/list.h. (Although namespace pollution is a
challenge, as commit ca64912c02bdff486fee420a49b11f54f8f5ba08 proved.) I
think this patch would be more clear with the generic data structure
code kept in separate files.
I hope someone will explain the XID reuse behavior. I've been told that
the X protocol spec permits the same XID to be used for multiple
resource types, as long as they don't conflict (like WINDOW and PIXMAP
do, through DRAWABLE). I've never been clear on how much that's really
supported or relied upon, though, or what the resource-free behavior is
supposed to be. It would be nice to have an example of a client that
does this, actually.
You'll want to be careful about the indentation in your patch when you
put the final version together for review. This version has several
different indentation levels throughout.
I hope those quick pseudo-review comments are helpful, despite not
really addressing the meat of your proposal...
Jamey
On Mon, May 27, 2013 at 11:56:06AM +0200, Roberto Ragusa wrote:
> 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
> _______________________________________________
> xorg-devel at lists.x.org: X.Org development
> Archives: http://lists.x.org/archives/xorg-devel
> Info: http://lists.x.org/mailman/listinfo/xorg-devel
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.x.org/archives/xorg-devel/attachments/20130527/2fa1d671/attachment-0001.pgp>
More information about the xorg-devel
mailing list