hw/xfree86/loader/loadext.c

   1 /*
   2  * Copyright (c) 2000 by The XFree86 Project, Inc.
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  17  * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR
  18  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  19  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  20  * OTHER DEALINGS IN THE SOFTWARE.
  21  *
  22  * Except as contained in this notice, the name of the copyright holder(s)
  23  * and author(s) shall not be used in advertising or otherwise to promote
  24  * the sale, use or other dealings in this Software without prior written
  25  * authorization from the copyright holder(s) and author(s).
  26  */
  27
  28 /* Maybe this file belongs elsewhere? */
  29
  30 #define LOADERDECLARATIONS
  31 #ifdef HAVE_XORG_CONFIG_H
  32 #include <xorg-config.h>
  33 #endif
  34
  35 #include "loaderProcs.h"
  36 #include "misc.h"
  37 #include "xf86.h"
  38
  39 /*
  40  * This should be static, but miinitext wants it.  FIXME: make extension
  41  * initialization not completely terrible.
  42  */
  43 ExtensionModule *ExtensionModuleList = NULL;
  44 static int numExtensionModules = 0;
  45
  46 static ExtensionModule *
  47 NewExtensionModule(void)
  48 {
  49     ExtensionModule *save = ExtensionModuleList;
  50     int n;
  51
  52     /* Sanity check */
  53     if (!ExtensionModuleList)
  54         numExtensionModules = 0;
  55
  56     n = numExtensionModules + 1;
  57     ExtensionModuleList = realloc(ExtensionModuleList,
  58                                    (n + 1) * sizeof(ExtensionModule));
  59     if (ExtensionModuleList == NULL) {
  60         ExtensionModuleList = save;
  61         return NULL;
  62     } else {
  63         numExtensionModules++;
  64         ExtensionModuleList[numExtensionModules].name = NULL;
  65         return ExtensionModuleList + (numExtensionModules - 1);
  66     }
  67 }
  68
  69 void
  70 LoadExtension(ExtensionModule * e, Bool builtin)
  71 {
  72     ExtensionModule *newext;
  73
  74     if (e == NULL || e->name == NULL)
  75         return;
  76
  77     if (!(newext = NewExtensionModule()))
  78         return;
  79
  80     if (builtin)
  81         xf86MsgVerb(X_INFO, 2, "Initializing built-in extension %s\n",
  82                     e->name);
  83     else
  84         xf86MsgVerb(X_INFO, 2, "Loading extension %s\n", e->name);
  85
  86     newext->name = e->name;
  87     newext->initFunc = e->initFunc;
  88     newext->disablePtr = e->disablePtr;
  89     newext->setupFunc = e->setupFunc;
  90     newext->initDependencies = e->initDependencies;
  91
  92     if (e->setupFunc != NULL)
  93         e->setupFunc();
  94 }
  95
  96 /*
  97  * Sort ExtensionModuleList according to the initialisation order
  98  * dependencies.  The code for this is taken from BSD's tsort,
  99  * and carries the following copyright/license:
 100  *
 101  *
 102  * Copyright (c) 1989, 1993, 1994
 103  *      The Regents of the University of California.  All rights reserved.
 104  *
 105  * This code is derived from software contributed to Berkeley by
 106  * Michael Rendell of Memorial University of Newfoundland.
 107  *
 108  * Redistribution and use in source and binary forms, with or without
 109  * modification, are permitted provided that the following conditions
 110  * are met:
 111  * 1. Redistributions of source code must retain the above copyright
 112  *    notice, this list of conditions and the following disclaimer.
 113  * 2. Redistributions in binary form must reproduce the above copyright
 114  *    notice, this list of conditions and the following disclaimer in the
 115  *    documentation and/or other materials provided with the distribution.
 116  * 3. All advertising materials mentioning features or use of this software
 117  *    must display the following acknowledgement:
 118  *      This product includes software developed by the University of
 119  *      California, Berkeley and its contributors.
 120  * 4. Neither the name of the University nor the names of its contributors
 121  *    may be used to endorse or promote products derived from this software
 122  *    without specific prior written permission.
 123  *
 124  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 125  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 126  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 127  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 128  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 129  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 130  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 131  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 132  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 133  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 134  * SUCH DAMAGE.
 135  */
 136
 137 #define NF_MARK         0x1     /* marker for cycle detection */
 138 #define NF_ACYCLIC      0x2     /* this node is cycle free */
 139 #define NF_NODEST       0x4     /* Unreachable */
 140
 141 typedef struct node_str NODE;
 142 struct node_str {
 143     NODE **n_prevp;             /* pointer to previous node's n_next */
 144     NODE *n_next;               /* next node in graph */
 145     NODE **n_arcs;              /* array of arcs to other nodes */
 146     int n_narcs;                /* number of arcs in n_arcs[] */
 147     int n_arcsize;              /* size of n_arcs[] array */
 148     int n_refcnt;               /* # of arcs pointing to this node */
 149     int n_flags;                /* NF_* */
 150     const char *n_name;         /* name of this node */
 151 };
 152
 153 static NODE *graph = NULL, **cycle_buf = NULL, **longest_cycle = NULL;
 154 static int longest = 0;
 155 static NODE *sorted = NULL, *last = NULL;
 156
 157 /* Find a node in the graph (insert if not found) and return a pointer to it. */
 158 static NODE *
 159 get_node(const char *name)
 160 {
 161     NODE *n;
 162
 163     for (n = graph; n && n->n_name && strcmp(n->n_name, name);
 164          n = n->n_next) ;
 165     if (n)
 166         return n;
 167
 168     n = xnfalloc(sizeof(NODE));
 169
 170     n->n_narcs = 0;
 171     n->n_arcsize = 0;
 172     n->n_arcs = NULL;
 173     n->n_refcnt = 0;
 174     n->n_flags = 0;
 175     n->n_name = name;
 176
 177     /* Add to linked list. */
 178     if ((n->n_next = graph) != NULL)
 179         graph->n_prevp = &n->n_next;
 180     n->n_prevp = &graph;
 181     graph = n;
 182
 183     return n;
 184 }
 185
 186 /*
 187  * add an arc from node s1 to node s2 in the graph.  If s1 or s2 are not in
 188  * the graph, then add them.
 189  */
 190 static void
 191 add_arc(const char *s1, const char *s2)
 192 {
 193     NODE *n1;
 194     NODE *n2;
 195     int bsize, i;
 196
 197     n1 = get_node(s1);
 198
 199     if (!strcmp(s1, s2))
 200         return;
 201
 202     n2 = get_node(s2);
 203
 204     /*
 205      * Check if this arc is already here.
 206      */
 207     for (i = 0; i < n1->n_narcs; i++)
 208         if (n1->n_arcs[i] == n2)
 209             return;
 210     /*
 211      * Add it.
 212      */
 213     if (n1->n_narcs == n1->n_arcsize) {
 214         if (!n1->n_arcsize)
 215             n1->n_arcsize = 10;
 216         bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;
 217         n1->n_arcs = xnfrealloc(n1->n_arcs, bsize);
 218         n1->n_arcsize = bsize / sizeof(*n1->n_arcs);
 219     }
 220     n1->n_arcs[n1->n_narcs++] = n2;
 221     ++n2->n_refcnt;
 222 }
 223
 224 /*
 225  * Clear the NODEST flag from all nodes.
 226  */
 227 static void
 228 clear_cycle(void)
 229 {
 230     NODE *n;
 231
 232     for (n = graph; n != NULL; n = n->n_next)
 233         n->n_flags &= ~NF_NODEST;
 234 }
 235
 236 /* print node and remove from graph (does not actually free node) */
 237 static void
 238 remove_node(NODE * n)
 239 {
 240     NODE **np;
 241     NODE *newnode;
 242     int i;
 243
 244 #ifdef DEBUG
 245     ErrorF("%s\n", n->n_name);
 246 #endif
 247     newnode = xnfalloc(sizeof(NODE));
 248     memcpy(newnode, n, sizeof(NODE));
 249     if (last)
 250         last->n_next = newnode;
 251     else
 252         sorted = newnode;
 253     last = newnode;
 254     newnode->n_next = NULL;
 255
 256     for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++)
 257         --(*np)->n_refcnt;
 258     n->n_narcs = 0;
 259     *n->n_prevp = n->n_next;
 260     if (n->n_next)
 261         n->n_next->n_prevp = n->n_prevp;
 262 }
 263
 264 static void
 265 free_nodes(NODE * nodelist)
 266 {
 267     NODE *n, *nextnode;
 268
 269     for (n = nodelist; n;) {
 270         nextnode = n->n_next;
 271         free(n);
 272         n = nextnode;
 273     }
 274 }
 275
 276 /* look for the longest? cycle from node from to node to. */
 277 static int
 278 find_cycle(NODE * from, NODE * to, int longest_len, int depth)
 279 {
 280     NODE **np;
 281     int i, len;
 282
 283     /*
 284      * avoid infinite loops and ignore portions of the graph known
 285      * to be acyclic
 286      */
 287     if (from->n_flags & (NF_NODEST | NF_MARK | NF_ACYCLIC))
 288         return 0;
 289     from->n_flags |= NF_MARK;
 290
 291     for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) {
 292         cycle_buf[depth] = *np;
 293         if (*np == to) {
 294             if (depth + 1 > longest_len) {
 295                 longest_len = depth + 1;
 296                 memcpy((char *)longest_cycle,
 297                        (char *)cycle_buf, longest_len * sizeof(NODE *));
 298             }
 299         } else {
 300             if ((*np)->n_flags & (NF_MARK | NF_ACYCLIC | NF_NODEST))
 301                 continue;
 302             len = find_cycle(*np, to, longest_len, depth + 1);
 303
 304 #ifdef DEBUG
 305             ErrorF("%*s %s->%s %d\n", depth, "",
 306                    from->n_name, to->n_name, len);
 307 #endif
 308
 309             if (len == 0)
 310                 (*np)->n_flags |= NF_NODEST;
 311
 312             if (len > longest_len)
 313                 longest_len = len;
 314
 315             if (len > 0 && !longest)
 316                 break;
 317         }
 318     }
 319     from->n_flags &= ~NF_MARK;
 320     return longest_len;
 321 }
 322
 323 /* do topological sort on graph */
 324 static void
 325 tsort(void)
 326 {
 327     NODE *n, *next;
 328     int cnt, i;
 329
 330     while (graph != NULL) {
 331         /*
 332          * Keep getting rid of simple cases until there are none left,
 333          * if there are any nodes still in the graph, then there is
 334          * a cycle in it.
 335          */
 336         do {
 337             for (cnt = 0, n = graph; n != NULL; n = next) {
 338                 next = n->n_next;
 339                 if (n->n_refcnt == 0) {
 340                     remove_node(n);
 341                     ++cnt;
 342                 }
 343             }
 344         } while (graph != NULL && cnt);
 345
 346         if (graph == NULL)
 347             break;
 348
 349         if (!cycle_buf) {
 350             /*
 351              * Allocate space for two cycle logs - one to be used
 352              * as scratch space, the other to save the longest
 353              * cycle.
 354              */
 355             for (cnt = 0, n = graph; n != NULL; n = n->n_next)
 356                 ++cnt;
 357             cycle_buf = xnfalloc(sizeof(NODE *) * cnt);
 358             longest_cycle = xnfalloc(sizeof(NODE *) * cnt);
 359             if (cycle_buf == NULL || longest_cycle == NULL)
 360                 return;
 361         }
 362         for (n = graph; n != NULL; n = n->n_next)
 363             if (!(n->n_flags & NF_ACYCLIC)) {
 364                 if ((cnt = find_cycle(n, n, 0, 0))) {
 365                     ErrorF("tsort: cycle in data");
 366                     for (i = 0; i < cnt; i++)
 367                         ErrorF("%s", longest_cycle[i]->n_name);
 368                     remove_node(n);
 369                     clear_cycle();
 370                     break;
 371                 } else {
 372                     /* to avoid further checks */
 373                     n->n_flags |= NF_ACYCLIC;
 374                     clear_cycle();
 375                 }
 376             }
 377
 378         if (n == NULL)
 379             ErrorF("tsort: internal error -- could not find cycle");
 380     }
 381     free(cycle_buf);
 382     free(longest_cycle);
 383     if (graph)
 384         free_nodes(graph);
 385 }
 386
 387 void
 388 LoaderSortExtensions(void)
 389 {
 390     int i, j;
 391     ExtensionModule *ext, *newList;
 392     NODE *node;
 393
 394     graph = NULL;
 395     longest = 0;
 396     sorted = NULL;
 397     last = NULL;
 398     cycle_buf = NULL;
 399     longest_cycle = NULL;
 400
 401     /*
 402      * Parse list and build the graph.  Enter them in reverse order
 403      * because tsort() will reverse those that have no depedencies.
 404      */
 405     for (i = numExtensionModules - 1; i >= 0; i--) {
 406         ext = &ExtensionModuleList[i];
 407         add_arc(ext->name, ext->name);
 408 #ifdef DEBUG
 409         ErrorF("Extension %s:\n", ext->name);
 410 #endif
 411         if (ext->initDependencies)
 412             for (j = 0; ext->initDependencies[j]; j++) {
 413                 add_arc(ext->initDependencies[j], ext->name);
 414 #ifdef DEBUG
 415                 ErrorF("\t%s\n", ext->initDependencies[j]);
 416 #endif
 417             }
 418     }
 419     tsort();
 420     newList = xnfalloc((numExtensionModules + 1) * sizeof(ExtensionModule));
 421     i = 0;
 422     for (node = sorted; node; node = node->n_next) {
 423         for (j = 0; j < numExtensionModules; j++)
 424             if (!strcmp(node->n_name, ExtensionModuleList[j].name))
 425                 break;
 426         if (j != numExtensionModules)
 427             newList[i++] = ExtensionModuleList[j];
 428     }
 429     if (sorted)
 430         free_nodes(sorted);
 431     if (graph)
 432         free_nodes(graph);
 433     newList[i].name = NULL;
 434     free(ExtensionModuleList);
 435     ExtensionModuleList = newList;
 436 #ifdef DEBUG
 437     for (i = 0; ExtensionModuleList[i].name; i++)
 438         ErrorF("Extension %s\n", ExtensionModuleList[i].name);
 439 #endif
 440 }