/* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License (the "License"). * You may not use this file except in compliance with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or http://www.opensolaris.org/os/licensing. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* * Copyright (c) 1996, 2010, Oracle and/or its affiliates. All rights reserved. */ /* * Utilities to handle shared object dependency graph. * * The algorithms used in this file are taken from the following book: * Algorithms in C * Robert Sedgewick * Addison-Wesley Publishing company * ISBN 0-201-51425-7 * From the following chapters: * Chapter 29 Elementary Graph Algorithms * Chapter 32 Directed Graph */ #include <sys/types.h> #include <stdarg.h> #include <stdio.h> #include <dlfcn.h> #include <signal.h> #include <locale.h> #include <string.h> #include <libintl.h> #include <debug.h> #include "_rtld.h" #include "msg.h" /* * Structure for maintaining sorting state. */ typedef struct { Rt_map **s_lmpa; /* link-map[] (returned to caller) */ Rt_map *s_lmp; /* originating link-map */ Rt_map **s_stack; /* strongly connected component stack */ APlist *s_scc; /* cyclic list */ APlist *s_queue; /* depth queue for cyclic components */ int s_sndx; /* present stack index */ int s_lndx; /* present link-map index */ int s_num; /* number of objects to sort */ int s_initfirst; /* no. of INITFIRST entries */ } Sort; #define AL_CNT_SCC 10 /* * qsort(3c) comparison function. */ static int compare(const void *lmpp1, const void *lmpp2) { Rt_map *lmp1 = *((Rt_map **)lmpp1); Rt_map *lmp2 = *((Rt_map **)lmpp2); if (IDX(lmp1) > IDX(lmp2)) return (-1); if (IDX(lmp1) < IDX(lmp2)) return (1); return (0); } /* * This routine is called when a cyclic dependency is detected between strongly * connected components. The nodes within the cycle are reverse breadth-first * sorted. */ static int sort_scc(Sort *sort, int fndx, int flag) { static const char *tfmt = 0, *ffmt; static int cnt = 1; int ndx; Rt_map *lmp; Lm_list *lml = LIST(sort->s_lmp); Word lmflags = lml->lm_flags; Word init, unref; /* * If this is the first cyclic dependency traverse the new objects that * have been added to the link-map list and for each object establish * a unique depth index. We build this dynamically as we have no idea * of the number of objects that will be inspected (logic matches that * used by dlsym() to traverse lazy dependencies). */ if (sort->s_queue == NULL) { Aliste idx1; Rt_map *lmp, *lmp2; lmp = sort->s_lmp; ndx = 1; if (aplist_append(&sort->s_queue, lmp, sort->s_num) == NULL) return (0); IDX(lmp) = ndx++; for (APLIST_TRAVERSE(sort->s_queue, idx1, lmp2)) { Bnd_desc *bdp; Aliste idx2; for (APLIST_TRAVERSE(DEPENDS(lmp2), idx2, bdp)) { Rt_map *lmp3 = bdp->b_depend; if (IDX(lmp3) || (LIST(lmp3) != lml)) continue; /* * If we're .init processing and this depend- * encies .init has been called, skip it. */ if ((flag & RT_SORT_REV) && (FLAGS(lmp3) & FLG_RT_INITCALL)) continue; if (aplist_append(&sort->s_queue, lmp3, sort->s_num) == NULL) return (0); IDX(lmp3) = ndx++; } } } /* * Sort the cyclics. */ qsort(&(sort->s_lmpa[fndx]), sort->s_lndx - fndx, sizeof (Rt_map *), compare); /* * Under ldd -i, or debugging, print this cycle. Under ldd -i/-U assign * each object a group identifier so that cyclic dependent callers can * be better traced (see trace_sort()), or analyzed for non-use. */ init = lmflags & LML_FLG_TRC_INIT; unref = lmflags & LML_FLG_TRC_UNREF; if ((init == 0) && (unref == 0) && (DBG_ENABLED == 0)) return (1); if (init) { if (tfmt == 0) { tfmt = MSG_INTL(MSG_LDD_INIT_FMT_01); ffmt = MSG_ORIG(MSG_LDD_INIT_FMT_FILE); } (void) printf(tfmt, cnt); } DBG_CALL(Dbg_util_scc_title(lml, (flag & RT_SORT_REV))); /* * Identify this cyclic group, and under ldd -i print the cycle in the * order its components will be run. */ if (flag & RT_SORT_REV) { for (ndx = fndx; ndx < sort->s_lndx; ndx++) { lmp = sort->s_lmpa[ndx]; CYCGROUP(lmp) = cnt; if (init) (void) printf(ffmt, NAME(lmp)); DBG_CALL(Dbg_util_scc_entry(lmp, ndx)); } cnt++; } else if (DBG_ENABLED) { for (ndx = sort->s_lndx - 1; ndx >= fndx; ndx--) { lmp = sort->s_lmpa[ndx]; DBG_CALL(Dbg_util_scc_entry(lmp, ndx)); } } /* * If we're looking for unused dependencies determine if any of these * cyclic components are referenced from outside of the cycle. */ if (unref || DBG_ENABLED) { for (ndx = fndx; ndx < sort->s_lndx; ndx++) { Bnd_desc *bdp; Aliste idx; lmp = sort->s_lmpa[ndx]; /* * If this object has a handle then it can be in use by * anyone. */ if (HANDLES(lmp)) return (1); /* * Traverse this objects callers looking for outside * references. */ for (APLIST_TRAVERSE(CALLERS(lmp), idx, bdp)) { Rt_map *clmp = bdp->b_caller; if ((bdp->b_flags & BND_REFER) == 0) continue; if (CYCGROUP(lmp) != CYCGROUP(clmp)) return (1); } } /* * If we're here then none of the cyclic dependents have been * referenced from outside of the cycle, mark them as unused. */ for (ndx = fndx; ndx < sort->s_lndx; ndx++) { lmp = sort->s_lmpa[ndx]; FLAGS1(lmp) &= ~FL1_RT_USED; } } return (1); } /* * Take elements off of the stack and move them to the link-map array. Typically * this routine just pops one strongly connected component (individual link-map) * at a time. When a cyclic dependency has been detected the stack will contain * more than just the present object to process, and will trigger the later call * to sort_scc() to sort these elements. */ static int visit(Lm_list *lml, Rt_map *lmp, Sort *sort, int flag) { APlist *alp = NULL; int num = sort->s_lndx; Word tracing = lml->lm_flags & LML_FLG_TRC_ENABLE; Rt_map *tlmp; do { tlmp = sort->s_stack[--(sort->s_sndx)]; SORTVAL(tlmp) = sort->s_num; DBG_CALL(Dbg_util_collect(tlmp, sort->s_lndx, flag)); sort->s_lmpa[(sort->s_lndx)++] = tlmp; if (flag & RT_SORT_REV) { /* * Indicate the object has had its .init collected. * Note, that regardless of the object having a .init * the object is added to the tsort list, as it's from * this list that any post-init flags are established. */ FLAGS(tlmp) |= FLG_RT_INITCLCT; lml->lm_init--; } else { /* * Indicate the object has had its .fini collected. * Note, that regardless of the object having a .fini, * the object is added to the tsort list, as it's from * this list that any audit_objclose() activity is * triggered. */ FLAGS(tlmp) |= FLG_RT_FINICLCT; } /* * If tracing, save the strongly connected component. */ if (tracing && (aplist_append(&alp, tlmp, AL_CNT_SCC) == NULL)) return (0); } while (tlmp != lmp); /* * Determine if there are cyclic dependencies to process. If so, sort * the components, and retain them for tracing output. */ if (sort->s_lndx > (num + 1)) { if (sort_scc(sort, num, flag) == 0) return (0); if (tracing && (aplist_append(&sort->s_scc, alp, AL_CNT_SCC) == NULL)) return (0); } else if (alp) free(alp); return (1); } static int dep_visit(Lm_list *, Rt_map *, uint_t, Rt_map *, Sort *, int); static int _dep_visit(Lm_list *lml, int min, Rt_map *clmp, Rt_map *dlmp, uint_t bflags, Sort *sort, int flag) { int _min; /* * Only collect objects that belong to the callers link-map. Catches * cross dependencies (filtering) to ld.so.1. */ if (LIST(dlmp) != lml) return (min); /* * Determine if this object hasn't been inspected. */ if ((_min = SORTVAL(dlmp)) == -1) { if (flag & RT_SORT_REV) { /* * For .init processing, only collect objects that have * been relocated and haven't already been collected. */ if ((FLAGS(dlmp) & (FLG_RT_RELOCED | FLG_RT_INITCLCT)) != FLG_RT_RELOCED) return (min); /* * If this object contains no .init, there's no need to * establish a dependency. */ if ((INIT(dlmp) == 0) && (INITARRAY(dlmp) == 0)) return (min); } else { /* * For .fini processing only collect objects that have * had their .init collected, and haven't already been * .fini collected. */ if ((FLAGS(dlmp) & (FLG_RT_INITCLCT | FLG_RT_FINICLCT)) != FLG_RT_INITCLCT) return (min); /* * If we're deleting a subset of objects, only collect * those marked for deletion. */ if ((flag & RT_SORT_DELETE) && ((FLAGS(dlmp) & FLG_RT_DELETE) == 0)) return (min); /* * If this object contains no .fini, there's no need to * establish a dependency. */ if ((FINI(dlmp) == 0) && (FINIARRAY(dlmp) == 0)) return (min); } /* * Inspect this new dependency. */ if ((_min = dep_visit(lml, clmp, bflags, dlmp, sort, flag)) == -1) return (-1); } /* * Keep track of the smallest SORTVAL that has been encountered. If * this value is smaller than the present object, then the dependency * edge has cycled back to objects that have been processed earlier * along this dependency edge. */ if (_min < min) { DBG_CALL(Dbg_util_edge_out(clmp, sort->s_stack[_min])); return (_min); } else return (min); } /* * Visit the dependencies of each object. */ static int dep_visit(Lm_list *lml, Rt_map *clmp, uint_t cbflags, Rt_map *lmp, Sort *sort, int flag) { int min; Aliste idx1; Bnd_desc *bdp; Dyninfo *dip; min = SORTVAL(lmp) = sort->s_sndx; sort->s_stack[(sort->s_sndx)++] = lmp; if (FLAGS(lmp) & FLG_RT_INITFRST) sort->s_initfirst++; DBG_CALL(Dbg_util_edge_in(lml, clmp, cbflags, lmp, min, flag)); /* * Traverse both explicit and implicit dependencies. */ for (APLIST_TRAVERSE(DEPENDS(lmp), idx1, bdp)) { if ((min = _dep_visit(lml, min, lmp, bdp->b_depend, bdp->b_flags, sort, flag)) == -1) return (-1); } /* * Traverse any filtee dependencies. */ if (((dip = DYNINFO(lmp)) != NULL) && (FLAGS1(lmp) & MSK_RT_FILTER)) { uint_t cnt, max = DYNINFOCNT(lmp); for (cnt = 0; cnt < max; cnt++, dip++) { Alist *falp; Pdesc *pdp; if (((falp = (Alist *)dip->di_info) == NULL) || ((dip->di_flags & MSK_DI_FILTER) == 0)) continue; for (ALIST_TRAVERSE(falp, idx1, pdp)) { Aliste idx2; Grp_hdl *ghp; Grp_desc *gdp; if ((pdp->pd_plen == 0) || ((ghp = (Grp_hdl *)pdp->pd_info) == NULL)) continue; for (ALIST_TRAVERSE(ghp->gh_depends, idx2, gdp)) { if (gdp->gd_depend == lmp) continue; if ((min = _dep_visit(lml, min, lmp, gdp->gd_depend, BND_FILTER, sort, flag)) == -1) return (-1); } } } } /* * Having returned to where the minimum SORTVAL is equivalent to the * object that has just been processed, collect any dependencies that * are available on the sorting stack. */ if (min == SORTVAL(lmp)) { if (visit(lml, lmp, sort, flag) == 0) return (-1); } return (min); } /* * Find corresponding strongly connected component structure. */ static APlist * trace_find_scc(Sort *sort, Rt_map *lmp) { APlist *alp; Aliste idx1; for (APLIST_TRAVERSE(sort->s_scc, idx1, alp)) { Rt_map *lmp2; Aliste idx2; for (APLIST_TRAVERSE(alp, idx2, lmp2)) { if (lmp == lmp2) return (alp); } } return (NULL); } /* * Print out the .init dependency information (ldd). */ static void trace_sort(Sort *sort) { int ndx = 0; APlist *alp; Rt_map *lmp1; (void) printf(MSG_ORIG(MSG_STR_NL)); while ((lmp1 = sort->s_lmpa[ndx++]) != NULL) { static const char *ffmt, *cfmt = 0, *sfmt = 0; Bnd_desc *bdp; Aliste idx1; if ((INIT(lmp1) == 0) || (FLAGS(lmp1) & FLG_RT_INITCALL)) continue; if (sfmt == 0) sfmt = MSG_INTL(MSG_LDD_INIT_FMT_02); /* * If the only component on the strongly connected list is * this link-map, then there are no dependencies. */ if ((alp = trace_find_scc(sort, lmp1)) == NULL) { (void) printf(sfmt, NAME(lmp1)); continue; } /* * Establish message formats for cyclic dependencies. */ if (cfmt == 0) { cfmt = MSG_INTL(MSG_LDD_INIT_FMT_03); ffmt = MSG_ORIG(MSG_LDD_INIT_FMT_FILE); } (void) printf(cfmt, NAME(lmp1), CYCGROUP(lmp1)); for (APLIST_TRAVERSE(CALLERS(lmp1), idx1, bdp)) { Rt_map *lmp3, *lmp2 = bdp->b_caller; Aliste idx2; for (APLIST_TRAVERSE(alp, idx2, lmp3)) { if (lmp2 != lmp3) continue; (void) printf(ffmt, NAME(lmp3)); } } } } /* * A reverse ordered list (for .init's) contains INITFIRST elements. Move each * of these elements to the front of the list. */ static void r_initfirst(Sort * sort, int end) { Rt_map *tlmp; int bgn, ifst, lifst = 0; for (bgn = 0; bgn < sort->s_initfirst; bgn++) { for (ifst = lifst; ifst <= end; ifst++) { tlmp = sort->s_lmpa[ifst]; if (!(FLAGS(tlmp) & FLG_RT_INITFRST)) continue; /* * If the INITFIRST element is already at the front of * the list leave it there. */ if (ifst == bgn) { lifst = ifst + 1; break; } /* * Move the elements from the front of the list up to * the INITFIRST element, back one position. */ (void) memmove(&sort->s_lmpa[bgn + 1], &sort->s_lmpa[bgn], ((ifst - bgn) * sizeof (Rt_map *))); /* * Insert INITFIRST element at the front of the list. */ sort->s_lmpa[bgn] = tlmp; lifst = ifst + 1; break; } } } /* * A forward ordered list (for .fini's) contains INITFIRST elements. Move each * of these elements to the front of the list. */ static void f_initfirst(Sort *sort, int end) { Rt_map *tlmp; int bgn, ifst, lifst = 0; for (bgn = 0; bgn < sort->s_initfirst; bgn++) { for (ifst = lifst; ifst <= end; ifst++) { tlmp = sort->s_lmpa[ifst]; if (!(FLAGS(tlmp) & FLG_RT_INITFRST)) continue; /* * If the INITFIRST element is already at the end of * the list leave it there. */ if (ifst == end) break; /* * Move the elements from after the INITFIRST element * up to the back of the list, up one position. */ (void) memmove(&sort->s_lmpa[ifst], &sort->s_lmpa[ifst + 1], ((end - ifst) * sizeof (Rt_map *))); /* * Insert INITFIRST element at the back of the list. */ sort->s_lmpa[end--] = tlmp; lifst = ifst; break; } } } /* * Determine whether .init or .fini processing is required. */ static int initorfini(Lm_list *lml, Rt_map *lmp, int flag, Sort *sort) { if (flag & RT_SORT_REV) { /* * For .init processing, only collect objects that have been * relocated and haven't already been collected. */ if ((FLAGS(lmp) & (FLG_RT_RELOCED | FLG_RT_INITCLCT)) != FLG_RT_RELOCED) return (0); if (dep_visit(lml, 0, 0, lmp, sort, flag) == -1) return (1); } else if (!(flag & RT_SORT_DELETE) || (FLAGS(lmp) & FLG_RT_DELETE)) { /* * Only collect objects that have had their .init collected, * and haven't already been .fini collected. */ if (!((FLAGS(lmp) & (FLG_RT_INITCLCT | FLG_RT_FINICLCT)) == (FLG_RT_INITCLCT))) return (0); if (dep_visit(lml, 0, 0, lmp, sort, flag) == -1) return (1); } return (0); } /* * Sort the dependency */ Rt_map ** tsort(Rt_map *lmp, int num, int flag) { Rt_map *_lmp; Lm_list *lml = LIST(lmp); Word init = lml->lm_flags & LML_FLG_TRC_INIT; Sort sort = { 0 }; size_t size; if (num == 0) return (0); /* * Prior to tsorting any .init sections, insure that the `environ' * symbol is initialized for this link-map list. */ if ((flag & RT_SORT_REV) && ((lml->lm_flags & (LML_FLG_TRC_ENABLE | LML_FLG_ENVIRON)) == 0)) set_environ(lml); /* * Allocate memory for link-map list array. Calloc the array to insure * all elements are zero, we might find that no objects need processing. * At the same time, allocate a stack for any topological sorting that * might be necessary. */ sort.s_lmp = lmp; sort.s_num = num + 1; size = sort.s_num * sizeof (Rt_map *); if ((sort.s_lmpa = calloc(2, size)) == NULL) return ((Rt_map **)S_ERROR); sort.s_stack = (Rt_map **)((uintptr_t)sort.s_lmpa + size); /* * Determine where to start searching for tsort() candidates. Any call * to tsort() for .init processing is passed the link-map from which to * start searching. However, if new objects have dependencies on * existing objects, or existing objects have been promoted (RTLD_LAZY * to RTLD_NOW), then start searching at the head of the link-map list. * These previously loaded objects will have been tagged for inclusion * in this tsort() pass. They still remain on an existing tsort() list, * which must have been prempted for control to have arrived here. * However, they will be ignored when encountered on any previous * tsort() list if their .init has already been called. */ if (lml->lm_flags & LML_FLG_OBJREEVAL) _lmp = lml->lm_head; else _lmp = lmp; DBG_CALL(Dbg_file_bindings(_lmp, flag)); lml->lm_flags &= ~(LML_FLG_OBJREEVAL | LML_FLG_OBJADDED | LML_FLG_OBJDELETED); /* * If interposers exist, inspect these objects first. * * Interposers can provide implicit dependencies - for example, an * application that has a dependency on libumem will caused any other * dependencies of the application that use the malloc family, to * have an implicit dependency on libumem. However, under the default * condition of lazy binding, these dependency relationships on libumem * are unknown to the tsorting process (ie. a call to one of the malloc * family has not occurred to establish the dependency). This lack of * dependency information makes the interposer look "standalone", * whereas the interposers .init/.fini should be analyzed with respect * to the dependency relationship libumem will eventually create. * * By inspecting interposing objects first, we are able to trigger * their .init sections to be accounted for before any others. * Selecting these .init sections first is important for the malloc * libraries, as these libraries need to prepare for pthread_atfork(). * However, handling interposer libraries in this generic fashion * should help provide for other dependency relationships that may * exist. */ if ((lml->lm_flags & (LML_FLG_INTRPOSE | LML_FLG_INTRPOSETSORT)) == LML_FLG_INTRPOSE) { Rt_map *ilmp = _lmp; /* * Unless the executable is tagged as an interposer, skip to * the next object. */ if ((FLAGS(ilmp) & MSK_RT_INTPOSE) == 0) ilmp = NEXT_RT_MAP(ilmp); for (; ilmp; ilmp = NEXT_RT_MAP(ilmp)) { if ((FLAGS(ilmp) & MSK_RT_INTPOSE) == 0) break; if (initorfini(lml, ilmp, (flag | RT_SORT_INTPOSE), &sort) != 0) return ((Rt_map **)S_ERROR); } /* * Once all interposers are processed, there is no need to * look for interposers again. An interposer can only * be introduced before any relocation takes place, thus * interposer .init's will be grabbed during the first tsort * starting at the head of the link-map list. * * Interposers can't be unloaded. Thus interposer .fini's can * only be called during atexit() processing. The interposer * tsort flag is removed from each link-map list during * atexit_fini() so that the interposers .fini sections are * processed appropriately. */ lml->lm_flags |= LML_FLG_INTRPOSETSORT; } /* * Inspect any standard objects. */ for (; _lmp; _lmp = NEXT_RT_MAP(_lmp)) { if (FLAGS(_lmp) & MSK_RT_INTPOSE) continue; if (initorfini(lml, _lmp, flag, &sort) != 0) return ((Rt_map **)S_ERROR); } /* * The dependencies have been collected such that they are appropriate * for an .init order, for .fini order reverse them. */ if (flag & RT_SORT_FWD) { int bgn = 0, end = sort.s_lndx - 1; while (bgn < end) { Rt_map *tlmp = sort.s_lmpa[end]; sort.s_lmpa[end] = sort.s_lmpa[bgn]; sort.s_lmpa[bgn] = tlmp; bgn++, end--; } } /* * If INITFIRST objects have been collected then move them to the front * or end of the list as appropriate. */ if (sort.s_initfirst) { if (flag & RT_SORT_REV) r_initfirst(&sort, sort.s_lndx - 1); else f_initfirst(&sort, sort.s_lndx - 1); } /* * If tracing .init sections (only meaningful for RT_SORT_REV), print * out the sorted dependencies. */ if (init) trace_sort(&sort); /* * Clean any temporary structures prior to return. */ if (sort.s_queue) { Aliste idx; Rt_map *lmp2; /* * Traverse the link-maps collected on the sort queue and * delete the depth index. These link-maps may be traversed * again to sort other components either for inits, and almost * certainly for .finis. */ for (APLIST_TRAVERSE(sort.s_queue, idx, lmp2)) IDX(lmp2) = 0; free(sort.s_queue); } if (sort.s_scc) { Aliste idx; APlist *alp; for (APLIST_TRAVERSE(sort.s_scc, idx, alp)) free(alp); free(sort.s_scc); } /* * The caller is responsible for freeing the sorted link-map list once * the associated .init/.fini's have been fired. */ DBG_CALL(Dbg_file_bindings_done(lml)); return (sort.s_lmpa); }
