gcc/testsuite/gcc.dg/pr18241-1.c

   1 /* { dg-do run } */
   2 /* { dg-options "-std=gnu99 -Wall -Wextra -O1" } */
   3
   4 extern void *memset (void*, int, unsigned long);
   5 extern void abort (void);
   6
   7 struct radix_tree_root {
   8         unsigned int height;
   9         struct radix_tree_node *rnode;
  10 };
  11
  12 struct radix_tree_node {
  13         unsigned int count;
  14         void *slots[64];
  15         unsigned long tags[2][2];
  16 };
  17
  18 struct radix_tree_path {
  19         struct radix_tree_node *node, **slot;
  20         int offset;
  21 };
  22
  23 static unsigned long height_to_maxindex[7] =
  24 {0, 63, 4095, 262143, 16777215, 1073741823, 4294967295};
  25
  26 static inline void tag_clear(struct radix_tree_node *node, int tag, int offset)
  27 {
  28         int nr;
  29         volatile unsigned long *addr;
  30         int mask;
  31
  32         nr = offset;
  33         addr = &node->tags[tag][0];
  34
  35         addr += nr >> 5;
  36         mask = 1 << (nr & 0x1f);
  37         *addr &= ~mask;
  38 }
  39
  40 void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)
  41 {
  42         struct radix_tree_path path[7], *pathp = path;
  43         unsigned int height, shift;
  44         void *ret = 0;
  45
  46         height = root->height;
  47         if (index > height_to_maxindex[height])
  48                 goto out;
  49
  50         shift = (height - 1) * 6;
  51         pathp->node = 0;
  52         pathp->slot = &root->rnode;
  53
  54         while (height > 0) {
  55                 int offset;
  56
  57                 if (*pathp->slot == 0)
  58                         goto out;
  59
  60                 offset = (index >> shift) & (64-1);
  61                 pathp[1].offset = offset;
  62                 pathp[1].node = *pathp[0].slot;
  63                 pathp[1].slot = (struct radix_tree_node **)
  64                         (pathp[1].node->slots + offset);
  65                 pathp++;
  66                 shift -= 6;
  67                 height--;
  68         }
  69
  70         ret = *pathp[0].slot;
  71         if (ret == 0)
  72                 goto out;
  73
  74         do {
  75                 int idx;
  76
  77                 tag_clear(pathp[0].node, tag, pathp[0].offset);
  78                 for (idx = 0; idx < 2; idx++) {
  79                         if (pathp[0].node->tags[tag][idx])
  80                                 goto out;
  81                 }
  82                 pathp--;
  83         } while (pathp[0].node);
  84 out:
  85         return ret;
  86 }
  87
  88 int main ()
  89 {
  90         struct radix_tree_root r;
  91         struct radix_tree_node node;
  92         void *p = (void *) 0xdeadbeef;
  93
  94         r.height = 1;
  95         r.rnode = &node;
  96
  97         memset (&node, 0, sizeof (node));
  98
  99         node.count = 1;
 100         node.slots [13] = p;
 101
 102         radix_tree_tag_clear (&r, 13, 1);
 103
 104         if (r.rnode->slots[13] != p)
 105                 abort ();
 106         return 0;
 107 }