diff options
Diffstat (limited to 'cddl/contrib/opensolaris/common')
| -rw-r--r-- | cddl/contrib/opensolaris/common/avl/avl.c | 969 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_create.c | 1366 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_decl.c | 184 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_error.c | 97 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_hash.c | 178 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_impl.h | 336 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_labels.c | 153 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_lookup.c | 313 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_open.c | 954 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_types.c | 845 | ||||
| -rw-r--r-- | cddl/contrib/opensolaris/common/ctf/ctf_util.c | 152 |
11 files changed, 5547 insertions, 0 deletions
diff --git a/cddl/contrib/opensolaris/common/avl/avl.c b/cddl/contrib/opensolaris/common/avl/avl.c new file mode 100644 index 0000000..7403e81 --- /dev/null +++ b/cddl/contrib/opensolaris/common/avl/avl.c @@ -0,0 +1,969 @@ +/* + * 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 2006 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + + +/* + * AVL - generic AVL tree implementation for kernel use + * + * A complete description of AVL trees can be found in many CS textbooks. + * + * Here is a very brief overview. An AVL tree is a binary search tree that is + * almost perfectly balanced. By "almost" perfectly balanced, we mean that at + * any given node, the left and right subtrees are allowed to differ in height + * by at most 1 level. + * + * This relaxation from a perfectly balanced binary tree allows doing + * insertion and deletion relatively efficiently. Searching the tree is + * still a fast operation, roughly O(log(N)). + * + * The key to insertion and deletion is a set of tree maniuplations called + * rotations, which bring unbalanced subtrees back into the semi-balanced state. + * + * This implementation of AVL trees has the following peculiarities: + * + * - The AVL specific data structures are physically embedded as fields + * in the "using" data structures. To maintain generality the code + * must constantly translate between "avl_node_t *" and containing + * data structure "void *"s by adding/subracting the avl_offset. + * + * - Since the AVL data is always embedded in other structures, there is + * no locking or memory allocation in the AVL routines. This must be + * provided for by the enclosing data structure's semantics. Typically, + * avl_insert()/_add()/_remove()/avl_insert_here() require some kind of + * exclusive write lock. Other operations require a read lock. + * + * - The implementation uses iteration instead of explicit recursion, + * since it is intended to run on limited size kernel stacks. Since + * there is no recursion stack present to move "up" in the tree, + * there is an explicit "parent" link in the avl_node_t. + * + * - The left/right children pointers of a node are in an array. + * In the code, variables (instead of constants) are used to represent + * left and right indices. The implementation is written as if it only + * dealt with left handed manipulations. By changing the value assigned + * to "left", the code also works for right handed trees. The + * following variables/terms are frequently used: + * + * int left; // 0 when dealing with left children, + * // 1 for dealing with right children + * + * int left_heavy; // -1 when left subtree is taller at some node, + * // +1 when right subtree is taller + * + * int right; // will be the opposite of left (0 or 1) + * int right_heavy;// will be the opposite of left_heavy (-1 or 1) + * + * int direction; // 0 for "<" (ie. left child); 1 for ">" (right) + * + * Though it is a little more confusing to read the code, the approach + * allows using half as much code (and hence cache footprint) for tree + * manipulations and eliminates many conditional branches. + * + * - The avl_index_t is an opaque "cookie" used to find nodes at or + * adjacent to where a new value would be inserted in the tree. The value + * is a modified "avl_node_t *". The bottom bit (normally 0 for a + * pointer) is set to indicate if that the new node has a value greater + * than the value of the indicated "avl_node_t *". + */ + +#include <sys/types.h> +#include <sys/param.h> +#include <sys/debug.h> +#include <sys/avl.h> +#include <sys/cmn_err.h> + +/* + * Small arrays to translate between balance (or diff) values and child indeces. + * + * Code that deals with binary tree data structures will randomly use + * left and right children when examining a tree. C "if()" statements + * which evaluate randomly suffer from very poor hardware branch prediction. + * In this code we avoid some of the branch mispredictions by using the + * following translation arrays. They replace random branches with an + * additional memory reference. Since the translation arrays are both very + * small the data should remain efficiently in cache. + */ +static const int avl_child2balance[2] = {-1, 1}; +static const int avl_balance2child[] = {0, 0, 1}; + + +/* + * Walk from one node to the previous valued node (ie. an infix walk + * towards the left). At any given node we do one of 2 things: + * + * - If there is a left child, go to it, then to it's rightmost descendant. + * + * - otherwise we return thru parent nodes until we've come from a right child. + * + * Return Value: + * NULL - if at the end of the nodes + * otherwise next node + */ +void * +avl_walk(avl_tree_t *tree, void *oldnode, int left) +{ + size_t off = tree->avl_offset; + avl_node_t *node = AVL_DATA2NODE(oldnode, off); + int right = 1 - left; + int was_child; + + + /* + * nowhere to walk to if tree is empty + */ + if (node == NULL) + return (NULL); + + /* + * Visit the previous valued node. There are two possibilities: + * + * If this node has a left child, go down one left, then all + * the way right. + */ + if (node->avl_child[left] != NULL) { + for (node = node->avl_child[left]; + node->avl_child[right] != NULL; + node = node->avl_child[right]) + ; + /* + * Otherwise, return thru left children as far as we can. + */ + } else { + for (;;) { + was_child = AVL_XCHILD(node); + node = AVL_XPARENT(node); + if (node == NULL) + return (NULL); + if (was_child == right) + break; + } + } + + return (AVL_NODE2DATA(node, off)); +} + +/* + * Return the lowest valued node in a tree or NULL. + * (leftmost child from root of tree) + */ +void * +avl_first(avl_tree_t *tree) +{ + avl_node_t *node; + avl_node_t *prev = NULL; + size_t off = tree->avl_offset; + + for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) + prev = node; + + if (prev != NULL) + return (AVL_NODE2DATA(prev, off)); + return (NULL); +} + +/* + * Return the highest valued node in a tree or NULL. + * (rightmost child from root of tree) + */ +void * +avl_last(avl_tree_t *tree) +{ + avl_node_t *node; + avl_node_t *prev = NULL; + size_t off = tree->avl_offset; + + for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) + prev = node; + + if (prev != NULL) + return (AVL_NODE2DATA(prev, off)); + return (NULL); +} + +/* + * Access the node immediately before or after an insertion point. + * + * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child + * + * Return value: + * NULL: no node in the given direction + * "void *" of the found tree node + */ +void * +avl_nearest(avl_tree_t *tree, avl_index_t where, int direction) +{ + int child = AVL_INDEX2CHILD(where); + avl_node_t *node = AVL_INDEX2NODE(where); + void *data; + size_t off = tree->avl_offset; + + if (node == NULL) { + ASSERT(tree->avl_root == NULL); + return (NULL); + } + data = AVL_NODE2DATA(node, off); + if (child != direction) + return (data); + + return (avl_walk(tree, data, direction)); +} + + +/* + * Search for the node which contains "value". The algorithm is a + * simple binary tree search. + * + * return value: + * NULL: the value is not in the AVL tree + * *where (if not NULL) is set to indicate the insertion point + * "void *" of the found tree node + */ +void * +avl_find(avl_tree_t *tree, void *value, avl_index_t *where) +{ + avl_node_t *node; + avl_node_t *prev = NULL; + int child = 0; + int diff; + size_t off = tree->avl_offset; + + for (node = tree->avl_root; node != NULL; + node = node->avl_child[child]) { + + prev = node; + + diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); + ASSERT(-1 <= diff && diff <= 1); + if (diff == 0) { +#ifdef DEBUG + if (where != NULL) + *where = 0; +#endif + return (AVL_NODE2DATA(node, off)); + } + child = avl_balance2child[1 + diff]; + + } + + if (where != NULL) + *where = AVL_MKINDEX(prev, child); + + return (NULL); +} + + +/* + * Perform a rotation to restore balance at the subtree given by depth. + * + * This routine is used by both insertion and deletion. The return value + * indicates: + * 0 : subtree did not change height + * !0 : subtree was reduced in height + * + * The code is written as if handling left rotations, right rotations are + * symmetric and handled by swapping values of variables right/left[_heavy] + * + * On input balance is the "new" balance at "node". This value is either + * -2 or +2. + */ +static int +avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) +{ + int left = !(balance < 0); /* when balance = -2, left will be 0 */ + int right = 1 - left; + int left_heavy = balance >> 1; + int right_heavy = -left_heavy; + avl_node_t *parent = AVL_XPARENT(node); + avl_node_t *child = node->avl_child[left]; + avl_node_t *cright; + avl_node_t *gchild; + avl_node_t *gright; + avl_node_t *gleft; + int which_child = AVL_XCHILD(node); + int child_bal = AVL_XBALANCE(child); + + /* BEGIN CSTYLED */ + /* + * case 1 : node is overly left heavy, the left child is balanced or + * also left heavy. This requires the following rotation. + * + * (node bal:-2) + * / \ + * / \ + * (child bal:0 or -1) + * / \ + * / \ + * cright + * + * becomes: + * + * (child bal:1 or 0) + * / \ + * / \ + * (node bal:-1 or 0) + * / \ + * / \ + * cright + * + * we detect this situation by noting that child's balance is not + * right_heavy. + */ + /* END CSTYLED */ + if (child_bal != right_heavy) { + + /* + * compute new balance of nodes + * + * If child used to be left heavy (now balanced) we reduced + * the height of this sub-tree -- used in "return...;" below + */ + child_bal += right_heavy; /* adjust towards right */ + + /* + * move "cright" to be node's left child + */ + cright = child->avl_child[right]; + node->avl_child[left] = cright; + if (cright != NULL) { + AVL_SETPARENT(cright, node); + AVL_SETCHILD(cright, left); + } + + /* + * move node to be child's right child + */ + child->avl_child[right] = node; + AVL_SETBALANCE(node, -child_bal); + AVL_SETCHILD(node, right); + AVL_SETPARENT(node, child); + + /* + * update the pointer into this subtree + */ + AVL_SETBALANCE(child, child_bal); + AVL_SETCHILD(child, which_child); + AVL_SETPARENT(child, parent); + if (parent != NULL) + parent->avl_child[which_child] = child; + else + tree->avl_root = child; + + return (child_bal == 0); + } + + /* BEGIN CSTYLED */ + /* + * case 2 : When node is left heavy, but child is right heavy we use + * a different rotation. + * + * (node b:-2) + * / \ + * / \ + * / \ + * (child b:+1) + * / \ + * / \ + * (gchild b: != 0) + * / \ + * / \ + * gleft gright + * + * becomes: + * + * (gchild b:0) + * / \ + * / \ + * / \ + * (child b:?) (node b:?) + * / \ / \ + * / \ / \ + * gleft gright + * + * computing the new balances is more complicated. As an example: + * if gchild was right_heavy, then child is now left heavy + * else it is balanced + */ + /* END CSTYLED */ + gchild = child->avl_child[right]; + gleft = gchild->avl_child[left]; + gright = gchild->avl_child[right]; + + /* + * move gright to left child of node and + * + * move gleft to right child of node + */ + node->avl_child[left] = gright; + if (gright != NULL) { + AVL_SETPARENT(gright, node); + AVL_SETCHILD(gright, left); + } + + child->avl_child[right] = gleft; + if (gleft != NULL) { + AVL_SETPARENT(gleft, child); + AVL_SETCHILD(gleft, right); + } + + /* + * move child to left child of gchild and + * + * move node to right child of gchild and + * + * fixup parent of all this to point to gchild + */ + balance = AVL_XBALANCE(gchild); + gchild->avl_child[left] = child; + AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0)); + AVL_SETPARENT(child, gchild); + AVL_SETCHILD(child, left); + + gchild->avl_child[right] = node; + AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0)); + AVL_SETPARENT(node, gchild); + AVL_SETCHILD(node, right); + + AVL_SETBALANCE(gchild, 0); + AVL_SETPARENT(gchild, parent); + AVL_SETCHILD(gchild, which_child); + if (parent != NULL) + parent->avl_child[which_child] = gchild; + else + tree->avl_root = gchild; + + return (1); /* the new tree is always shorter */ +} + + +/* + * Insert a new node into an AVL tree at the specified (from avl_find()) place. + * + * Newly inserted nodes are always leaf nodes in the tree, since avl_find() + * searches out to the leaf positions. The avl_index_t indicates the node + * which will be the parent of the new node. + * + * After the node is inserted, a single rotation further up the tree may + * be necessary to maintain an acceptable AVL balance. + */ +void +avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where) +{ + avl_node_t *node; + avl_node_t *parent = AVL_INDEX2NODE(where); + int old_balance; + int new_balance; + int which_child = AVL_INDEX2CHILD(where); + size_t off = tree->avl_offset; + + ASSERT(tree); +#ifdef _LP64 + ASSERT(((uintptr_t)new_data & 0x7) == 0); +#endif + + node = AVL_DATA2NODE(new_data, off); + + /* + * First, add the node to the tree at the indicated position. + */ + ++tree->avl_numnodes; + + node->avl_child[0] = NULL; + node->avl_child[1] = NULL; + + AVL_SETCHILD(node, which_child); + AVL_SETBALANCE(node, 0); + AVL_SETPARENT(node, parent); + if (parent != NULL) { + ASSERT(parent->avl_child[which_child] == NULL); + parent->avl_child[which_child] = node; + } else { + ASSERT(tree->avl_root == NULL); + tree->avl_root = node; + } + /* + * Now, back up the tree modifying the balance of all nodes above the + * insertion point. If we get to a highly unbalanced ancestor, we + * need to do a rotation. If we back out of the tree we are done. + * If we brought any subtree into perfect balance (0), we are also done. + */ + for (;;) { + node = parent; + if (node == NULL) + return; + + /* + * Compute the new balance + */ + old_balance = AVL_XBALANCE(node); + new_balance = old_balance + avl_child2balance[which_child]; + + /* + * If we introduced equal balance, then we are done immediately + */ + if (new_balance == 0) { + AVL_SETBALANCE(node, 0); + return; + } + + /* + * If both old and new are not zero we went + * from -1 to -2 balance, do a rotation. + */ + if (old_balance != 0) + break; + + AVL_SETBALANCE(node, new_balance); + parent = AVL_XPARENT(node); + which_child = AVL_XCHILD(node); + } + + /* + * perform a rotation to fix the tree and return + */ + (void) avl_rotation(tree, node, new_balance); +} + +/* + * Insert "new_data" in "tree" in the given "direction" either after or + * before (AVL_AFTER, AVL_BEFORE) the data "here". + * + * Insertions can only be done at empty leaf points in the tree, therefore + * if the given child of the node is already present we move to either + * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since + * every other node in the tree is a leaf, this always works. + * + * To help developers using this interface, we assert that the new node + * is correctly ordered at every step of the way in DEBUG kernels. + */ +void +avl_insert_here( + avl_tree_t *tree, + void *new_data, + void *here, + int direction) +{ + avl_node_t *node; + int child = direction; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */ +#ifdef DEBUG + int diff; +#endif + + ASSERT(tree != NULL); + ASSERT(new_data != NULL); + ASSERT(here != NULL); + ASSERT(direction == AVL_BEFORE || direction == AVL_AFTER); + + /* + * If corresponding child of node is not NULL, go to the neighboring + * node and reverse the insertion direction. + */ + node = AVL_DATA2NODE(here, tree->avl_offset); + +#ifdef DEBUG + diff = tree->avl_compar(new_data, here); + ASSERT(-1 <= diff && diff <= 1); + ASSERT(diff != 0); + ASSERT(diff > 0 ? child == 1 : child == 0); +#endif + + if (node->avl_child[child] != NULL) { + node = node->avl_child[child]; + child = 1 - child; + while (node->avl_child[child] != NULL) { +#ifdef DEBUG + diff = tree->avl_compar(new_data, + AVL_NODE2DATA(node, tree->avl_offset)); + ASSERT(-1 <= diff && diff <= 1); + ASSERT(diff != 0); + ASSERT(diff > 0 ? child == 1 : child == 0); +#endif + node = node->avl_child[child]; + } +#ifdef DEBUG + diff = tree->avl_compar(new_data, + AVL_NODE2DATA(node, tree->avl_offset)); + ASSERT(-1 <= diff && diff <= 1); + ASSERT(diff != 0); + ASSERT(diff > 0 ? child == 1 : child == 0); +#endif + } + ASSERT(node->avl_child[child] == NULL); + + avl_insert(tree, new_data, AVL_MKINDEX(node, child)); +} + +/* + * Add a new node to an AVL tree. + */ +void +avl_add(avl_tree_t *tree, void *new_node) +{ + avl_index_t where; + + /* + * This is unfortunate. We want to call panic() here, even for + * non-DEBUG kernels. In userland, however, we can't depend on anything + * in libc or else the rtld build process gets confused. So, all we can + * do in userland is resort to a normal ASSERT(). + */ + if (avl_find(tree, new_node, &where) != NULL) +#ifdef _KERNEL + panic("avl_find() succeeded inside avl_add()"); +#else + ASSERT(0); +#endif + avl_insert(tree, new_node, where); +} + +/* + * Delete a node from the AVL tree. Deletion is similar to insertion, but + * with 2 complications. + * + * First, we may be deleting an interior node. Consider the following subtree: + * + * d c c + * / \ / \ / \ + * b e b e b e + * / \ / \ / + * a c a a + * + * When we are deleting node (d), we find and bring up an adjacent valued leaf + * node, say (c), to take the interior node's place. In the code this is + * handled by temporarily swapping (d) and (c) in the tree and then using + * common code to delete (d) from the leaf position. + * + * Secondly, an interior deletion from a deep tree may require more than one + * rotation to fix the balance. This is handled by moving up the tree through + * parents and applying rotations as needed. The return value from + * avl_rotation() is used to detect when a subtree did not change overall + * height due to a rotation. + */ +void +avl_remove(avl_tree_t *tree, void *data) +{ + avl_node_t *delete; + avl_node_t *parent; + avl_node_t *node; + avl_node_t tmp; + int old_balance; + int new_balance; + int left; + int right; + int which_child; + size_t off = tree->avl_offset; + + ASSERT(tree); + + delete = AVL_DATA2NODE(data, off); + + /* + * Deletion is easiest with a node that has at most 1 child. + * We swap a node with 2 children with a sequentially valued + * neighbor node. That node will have at most 1 child. Note this + * has no effect on the ordering of the remaining nodes. + * + * As an optimization, we choose the greater neighbor if the tree + * is right heavy, otherwise the left neighbor. This reduces the + * number of rotations needed. + */ + if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) { + + /* + * choose node to swap from whichever side is taller + */ + old_balance = AVL_XBALANCE(delete); + left = avl_balance2child[old_balance + 1]; + right = 1 - left; + + /* + * get to the previous value'd node + * (down 1 left, as far as possible right) + */ + for (node = delete->avl_child[left]; + node->avl_child[right] != NULL; + node = node->avl_child[right]) + ; + + /* + * create a temp placeholder for 'node' + * move 'node' to delete's spot in the tree + */ + tmp = *node; + + *node = *delete; + if (node->avl_child[left] == node) + node->avl_child[left] = &tmp; + + parent = AVL_XPARENT(node); + if (parent != NULL) + parent->avl_child[AVL_XCHILD(node)] = node; + else + tree->avl_root = node; + AVL_SETPARENT(node->avl_child[left], node); + AVL_SETPARENT(node->avl_child[right], node); + + /* + * Put tmp where node used to be (just temporary). + * It always has a parent and at most 1 child. + */ + delete = &tmp; + parent = AVL_XPARENT(delete); + parent->avl_child[AVL_XCHILD(delete)] = delete; + which_child = (delete->avl_child[1] != 0); + if (delete->avl_child[which_child] != NULL) + AVL_SETPARENT(delete->avl_child[which_child], delete); + } + + + /* + * Here we know "delete" is at least partially a leaf node. It can + * be easily removed from the tree. + */ + ASSERT(tree->avl_numnodes > 0); + --tree->avl_numnodes; + parent = AVL_XPARENT(delete); + which_child = AVL_XCHILD(delete); + if (delete->avl_child[0] != NULL) + node = delete->avl_child[0]; + else + node = delete->avl_child[1]; + + /* + * Connect parent directly to node (leaving out delete). + */ + if (node != NULL) { + AVL_SETPARENT(node, parent); + AVL_SETCHILD(node, which_child); + } + if (parent == NULL) { + tree->avl_root = node; + return; + } + parent->avl_child[which_child] = node; + + + /* + * Since the subtree is now shorter, begin adjusting parent balances + * and performing any needed rotations. + */ + do { + + /* + * Move up the tree and adjust the balance + * + * Capture the parent and which_child values for the next + * iteration before any rotations occur. + */ + node = parent; + old_balance = AVL_XBALANCE(node); + new_balance = old_balance - avl_child2balance[which_child]; + parent = AVL_XPARENT(node); + which_child = AVL_XCHILD(node); + + /* + * If a node was in perfect balance but isn't anymore then + * we can stop, since the height didn't change above this point + * due to a deletion. + */ + if (old_balance == 0) { + AVL_SETBALANCE(node, new_balance); + break; + } + + /* + * If the new balance is zero, we don't need to rotate + * else + * need a rotation to fix the balance. + * If the rotation doesn't change the height + * of the sub-tree we have finished adjusting. + */ + if (new_balance == 0) + AVL_SETBALANCE(node, new_balance); + else if (!avl_rotation(tree, node, new_balance)) + break; + } while (parent != NULL); +} + +/* + * initialize a new AVL tree + */ +void +avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *), + size_t size, size_t offset) +{ + ASSERT(tree); + ASSERT(compar); + ASSERT(size > 0); + ASSERT(size >= offset + sizeof (avl_node_t)); +#ifdef _LP64 + ASSERT((offset & 0x7) == 0); +#endif + + tree->avl_compar = compar; + tree->avl_root = NULL; + tree->avl_numnodes = 0; + tree->avl_size = size; + tree->avl_offset = offset; +} + +/* + * Delete a tree. + */ +/* ARGSUSED */ +void +avl_destroy(avl_tree_t *tree) +{ + ASSERT(tree); + ASSERT(tree->avl_numnodes == 0); + ASSERT(tree->avl_root == NULL); +} + + +/* + * Return the number of nodes in an AVL tree. + */ +ulong_t +avl_numnodes(avl_tree_t *tree) +{ + ASSERT(tree); + return (tree->avl_numnodes); +} + + +#define CHILDBIT (1L) + +/* + * Post-order tree walk used to visit all tree nodes and destroy the tree + * in post order. This is used for destroying a tree w/o paying any cost + * for rebalancing it. + * + * example: + * + * void *cookie = NULL; + * my_data_t *node; + * + * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) + * free(node); + * avl_destroy(tree); + * + * The cookie is really an avl_node_t to the current node's parent and + * an indication of which child you looked at last. + * + * On input, a cookie value of CHILDBIT indicates the tree is done. + */ +void * +avl_destroy_nodes(avl_tree_t *tree, void **cookie) +{ + avl_node_t *node; + avl_node_t *parent; + int child; + void *first; + size_t off = tree->avl_offset; + + /* + * Initial calls go to the first node or it's right descendant. + */ + if (*cookie == NULL) { + first = avl_first(tree); + + /* + * deal with an empty tree + */ + if (first == NULL) { + *cookie = (void *)CHILDBIT; + return (NULL); + } + + node = AVL_DATA2NODE(first, off); + parent = AVL_XPARENT(node); + goto check_right_side; + } + + /* + * If there is no parent to return to we are done. + */ + parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT); + if (parent == NULL) { + if (tree->avl_root != NULL) { + ASSERT(tree->avl_numnodes == 1); + tree->avl_root = NULL; + tree->avl_numnodes = 0; + } + return (NULL); + } + + /* + * Remove the child pointer we just visited from the parent and tree. + */ + child = (uintptr_t)(*cookie) & CHILDBIT; + parent->avl_child[child] = NULL; + ASSERT(tree->avl_numnodes > 1); + --tree->avl_numnodes; + + /* + * If we just did a right child or there isn't one, go up to parent. + */ + if (child == 1 || parent->avl_child[1] == NULL) { + node = parent; + parent = AVL_XPARENT(parent); + goto done; + } + + /* + * Do parent's right child, then leftmost descendent. + */ + node = parent->avl_child[1]; + while (node->avl_child[0] != NULL) { + parent = node; + node = node->avl_child[0]; + } + + /* + * If here, we moved to a left child. It may have one + * child on the right (when balance == +1). + */ +check_right_side: + if (node->avl_child[1] != NULL) { + ASSERT(AVL_XBALANCE(node) == 1); + parent = node; + node = node->avl_child[1]; + ASSERT(node->avl_child[0] == NULL && + node->avl_child[1] == NULL); + } else { + ASSERT(AVL_XBALANCE(node) <= 0); + } + +done: + if (parent == NULL) { + *cookie = (void *)CHILDBIT; + ASSERT(node == tree->avl_root); + } else { + *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); + } + + return (AVL_NODE2DATA(node, off)); +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_create.c b/cddl/contrib/opensolaris/common/ctf/ctf_create.c new file mode 100644 index 0000000..a4f3df3 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_create.c @@ -0,0 +1,1366 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2006 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <sys/sysmacros.h> +#include <sys/param.h> +#include <sys/mman.h> +#include <ctf_impl.h> + +/* + * This static string is used as the template for initially populating a + * dynamic container's string table. We always store \0 in the first byte, + * and we use the generic string "PARENT" to mark this container's parent + * if one is associated with the container using ctf_import(). + */ +static const char _CTF_STRTAB_TEMPLATE[] = "\0PARENT"; + +/* + * To create an empty CTF container, we just declare a zeroed header and call + * ctf_bufopen() on it. If ctf_bufopen succeeds, we mark the new container r/w + * and initialize the dynamic members. We set dtstrlen to 1 to reserve the + * first byte of the string table for a \0 byte, and we start assigning type + * IDs at 1 because type ID 0 is used as a sentinel. + */ +ctf_file_t * +ctf_create(int *errp) +{ + static const ctf_header_t hdr = { { CTF_MAGIC, CTF_VERSION, 0 } }; + + const ulong_t hashlen = 128; + ctf_dtdef_t **hash = ctf_alloc(hashlen * sizeof (ctf_dtdef_t *)); + ctf_sect_t cts; + ctf_file_t *fp; + + if (hash == NULL) + return (ctf_set_open_errno(errp, EAGAIN)); + + cts.cts_name = _CTF_SECTION; + cts.cts_type = SHT_PROGBITS; + cts.cts_flags = 0; + cts.cts_data = &hdr; + cts.cts_size = sizeof (hdr); + cts.cts_entsize = 1; + cts.cts_offset = 0; + + if ((fp = ctf_bufopen(&cts, NULL, NULL, errp)) == NULL) { + ctf_free(hash, hashlen * sizeof (ctf_dtdef_t *)); + return (NULL); + } + + fp->ctf_flags |= LCTF_RDWR; + fp->ctf_dthashlen = hashlen; + bzero(hash, hashlen * sizeof (ctf_dtdef_t *)); + fp->ctf_dthash = hash; + fp->ctf_dtstrlen = sizeof (_CTF_STRTAB_TEMPLATE); + fp->ctf_dtnextid = 1; + fp->ctf_dtoldid = 0; + + return (fp); +} + +static uchar_t * +ctf_copy_smembers(ctf_dtdef_t *dtd, uint_t soff, uchar_t *t) +{ + ctf_dmdef_t *dmd = ctf_list_next(&dtd->dtd_u.dtu_members); + ctf_member_t ctm; + + for (; dmd != NULL; dmd = ctf_list_next(dmd)) { + if (dmd->dmd_name) { + ctm.ctm_name = soff; + soff += strlen(dmd->dmd_name) + 1; + } else + ctm.ctm_name = 0; + + ctm.ctm_type = (ushort_t)dmd->dmd_type; + ctm.ctm_offset = (ushort_t)dmd->dmd_offset; + + bcopy(&ctm, t, sizeof (ctm)); + t += sizeof (ctm); + } + + return (t); +} + +static uchar_t * +ctf_copy_lmembers(ctf_dtdef_t *dtd, uint_t soff, uchar_t *t) +{ + ctf_dmdef_t *dmd = ctf_list_next(&dtd->dtd_u.dtu_members); + ctf_lmember_t ctlm; + + for (; dmd != NULL; dmd = ctf_list_next(dmd)) { + if (dmd->dmd_name) { + ctlm.ctlm_name = soff; + soff += strlen(dmd->dmd_name) + 1; + } else + ctlm.ctlm_name = 0; + + ctlm.ctlm_type = (ushort_t)dmd->dmd_type; + ctlm.ctlm_pad = 0; + ctlm.ctlm_offsethi = CTF_OFFSET_TO_LMEMHI(dmd->dmd_offset); + ctlm.ctlm_offsetlo = CTF_OFFSET_TO_LMEMLO(dmd->dmd_offset); + + bcopy(&ctlm, t, sizeof (ctlm)); + t += sizeof (ctlm); + } + + return (t); +} + +static uchar_t * +ctf_copy_emembers(ctf_dtdef_t *dtd, uint_t soff, uchar_t *t) +{ + ctf_dmdef_t *dmd = ctf_list_next(&dtd->dtd_u.dtu_members); + ctf_enum_t cte; + + for (; dmd != NULL; dmd = ctf_list_next(dmd)) { + cte.cte_name = soff; + cte.cte_value = dmd->dmd_value; + soff += strlen(dmd->dmd_name) + 1; + bcopy(&cte, t, sizeof (cte)); + t += sizeof (cte); + } + + return (t); +} + +static uchar_t * +ctf_copy_membnames(ctf_dtdef_t *dtd, uchar_t *s) +{ + ctf_dmdef_t *dmd = ctf_list_next(&dtd->dtd_u.dtu_members); + size_t len; + + for (; dmd != NULL; dmd = ctf_list_next(dmd)) { + if (dmd->dmd_name == NULL) + continue; /* skip anonymous members */ + len = strlen(dmd->dmd_name) + 1; + bcopy(dmd->dmd_name, s, len); + s += len; + } + + return (s); +} + +/* + * If the specified CTF container is writable and has been modified, reload + * this container with the updated type definitions. In order to make this + * code and the rest of libctf as simple as possible, we perform updates by + * taking the dynamic type definitions and creating an in-memory CTF file + * containing the definitions, and then call ctf_bufopen() on it. This not + * only leverages ctf_bufopen(), but also avoids having to bifurcate the rest + * of the library code with different lookup paths for static and dynamic + * type definitions. We are therefore optimizing greatly for lookup over + * update, which we assume will be an uncommon operation. We perform one + * extra trick here for the benefit of callers and to keep our code simple: + * ctf_bufopen() will return a new ctf_file_t, but we want to keep the fp + * constant for the caller, so after ctf_bufopen() returns, we use bcopy to + * swap the interior of the old and new ctf_file_t's, and then free the old. + */ +int +ctf_update(ctf_file_t *fp) +{ + ctf_file_t ofp, *nfp; + ctf_header_t hdr; + ctf_dtdef_t *dtd; + ctf_sect_t cts; + + uchar_t *s, *s0, *t; + size_t size; + void *buf; + int err; + + if (!(fp->ctf_flags & LCTF_RDWR)) + return (ctf_set_errno(fp, ECTF_RDONLY)); + + if (!(fp->ctf_flags & LCTF_DIRTY)) + return (0); /* no update required */ + + /* + * Fill in an initial CTF header. We will leave the label, object, + * and function sections empty and only output a header, type section, + * and string table. The type section begins at a 4-byte aligned + * boundary past the CTF header itself (at relative offset zero). + */ + bzero(&hdr, sizeof (hdr)); + hdr.cth_magic = CTF_MAGIC; + hdr.cth_version = CTF_VERSION; + + if (fp->ctf_flags & LCTF_CHILD) + hdr.cth_parname = 1; /* i.e. _CTF_STRTAB_TEMPLATE[1] */ + + /* + * Iterate through the dynamic type definition list and compute the + * size of the CTF type section we will need to generate. + */ + for (size = 0, dtd = ctf_list_next(&fp->ctf_dtdefs); + dtd != NULL; dtd = ctf_list_next(dtd)) { + + uint_t kind = CTF_INFO_KIND(dtd->dtd_data.ctt_info); + uint_t vlen = CTF_INFO_VLEN(dtd->dtd_data.ctt_info); + + if (dtd->dtd_data.ctt_size != CTF_LSIZE_SENT) + size += sizeof (ctf_stype_t); + else + size += sizeof (ctf_type_t); + + switch (kind) { + case CTF_K_INTEGER: + case CTF_K_FLOAT: + size += sizeof (uint_t); + break; + case CTF_K_ARRAY: + size += sizeof (ctf_array_t); + break; + case CTF_K_FUNCTION: + size += sizeof (ushort_t) * (vlen + (vlen & 1)); + break; + case CTF_K_STRUCT: + case CTF_K_UNION: + if (dtd->dtd_data.ctt_size < CTF_LSTRUCT_THRESH) + size += sizeof (ctf_member_t) * vlen; + else + size += sizeof (ctf_lmember_t) * vlen; + break; + case CTF_K_ENUM: + size += sizeof (ctf_enum_t) * vlen; + break; + } + } + + /* + * Fill in the string table offset and size, compute the size of the + * entire CTF buffer we need, and then allocate a new buffer and + * bcopy the finished header to the start of the buffer. + */ + hdr.cth_stroff = hdr.cth_typeoff + size; + hdr.cth_strlen = fp->ctf_dtstrlen; + size = sizeof (ctf_header_t) + hdr.cth_stroff + hdr.cth_strlen; + + if ((buf = ctf_data_alloc(size)) == MAP_FAILED) + return (ctf_set_errno(fp, EAGAIN)); + + bcopy(&hdr, buf, sizeof (ctf_header_t)); + t = (uchar_t *)buf + sizeof (ctf_header_t); + s = s0 = (uchar_t *)buf + sizeof (ctf_header_t) + hdr.cth_stroff; + + bcopy(_CTF_STRTAB_TEMPLATE, s, sizeof (_CTF_STRTAB_TEMPLATE)); + s += sizeof (_CTF_STRTAB_TEMPLATE); + + /* + * We now take a final lap through the dynamic type definition list and + * copy the appropriate type records and strings to the output buffer. + */ + for (dtd = ctf_list_next(&fp->ctf_dtdefs); + dtd != NULL; dtd = ctf_list_next(dtd)) { + + uint_t kind = CTF_INFO_KIND(dtd->dtd_data.ctt_info); + uint_t vlen = CTF_INFO_VLEN(dtd->dtd_data.ctt_info); + + ctf_array_t cta; + uint_t encoding; + size_t len; + + if (dtd->dtd_name != NULL) { + dtd->dtd_data.ctt_name = (uint_t)(s - s0); + len = strlen(dtd->dtd_name) + 1; + bcopy(dtd->dtd_name, s, len); + s += len; + } else + dtd->dtd_data.ctt_name = 0; + + if (dtd->dtd_data.ctt_size != CTF_LSIZE_SENT) + len = sizeof (ctf_stype_t); + else + len = sizeof (ctf_type_t); + + bcopy(&dtd->dtd_data, t, len); + t += len; + + switch (kind) { + case CTF_K_INTEGER: + case CTF_K_FLOAT: + if (kind == CTF_K_INTEGER) { + encoding = CTF_INT_DATA( + dtd->dtd_u.dtu_enc.cte_format, + dtd->dtd_u.dtu_enc.cte_offset, + dtd->dtd_u.dtu_enc.cte_bits); + } else { + encoding = CTF_FP_DATA( + dtd->dtd_u.dtu_enc.cte_format, + dtd->dtd_u.dtu_enc.cte_offset, + dtd->dtd_u.dtu_enc.cte_bits); + } + bcopy(&encoding, t, sizeof (encoding)); + t += sizeof (encoding); + break; + + case CTF_K_ARRAY: + cta.cta_contents = (ushort_t) + dtd->dtd_u.dtu_arr.ctr_contents; + cta.cta_index = (ushort_t) + dtd->dtd_u.dtu_arr.ctr_index; + cta.cta_nelems = dtd->dtd_u.dtu_arr.ctr_nelems; + bcopy(&cta, t, sizeof (cta)); + t += sizeof (cta); + break; + + case CTF_K_FUNCTION: { + ushort_t *argv = (ushort_t *)(uintptr_t)t; + uint_t argc; + + for (argc = 0; argc < vlen; argc++) + *argv++ = (ushort_t)dtd->dtd_u.dtu_argv[argc]; + + if (vlen & 1) + *argv++ = 0; /* pad to 4-byte boundary */ + + t = (uchar_t *)argv; + break; + } + + case CTF_K_STRUCT: + case CTF_K_UNION: + if (dtd->dtd_data.ctt_size < CTF_LSTRUCT_THRESH) + t = ctf_copy_smembers(dtd, (uint_t)(s - s0), t); + else + t = ctf_copy_lmembers(dtd, (uint_t)(s - s0), t); + s = ctf_copy_membnames(dtd, s); + break; + + case CTF_K_ENUM: + t = ctf_copy_emembers(dtd, (uint_t)(s - s0), t); + s = ctf_copy_membnames(dtd, s); + break; + } + } + + /* + * Finally, we are ready to ctf_bufopen() the new container. If this + * is successful, we then switch nfp and fp and free the old container. + */ + ctf_data_protect(buf, size); + cts.cts_name = _CTF_SECTION; + cts.cts_type = SHT_PROGBITS; + cts.cts_flags = 0; + cts.cts_data = buf; + cts.cts_size = size; + cts.cts_entsize = 1; + cts.cts_offset = 0; + + if ((nfp = ctf_bufopen(&cts, NULL, NULL, &err)) == NULL) { + ctf_data_free(buf, size); + return (ctf_set_errno(fp, err)); + } + + (void) ctf_setmodel(nfp, ctf_getmodel(fp)); + (void) ctf_import(nfp, fp->ctf_parent); + + nfp->ctf_refcnt = fp->ctf_refcnt; + nfp->ctf_flags |= fp->ctf_flags & ~LCTF_DIRTY; + nfp->ctf_data.cts_data = NULL; /* force ctf_data_free() on close */ + nfp->ctf_dthash = fp->ctf_dthash; + nfp->ctf_dthashlen = fp->ctf_dthashlen; + nfp->ctf_dtdefs = fp->ctf_dtdefs; + nfp->ctf_dtstrlen = fp->ctf_dtstrlen; + nfp->ctf_dtnextid = fp->ctf_dtnextid; + nfp->ctf_dtoldid = fp->ctf_dtnextid - 1; + nfp->ctf_specific = fp->ctf_specific; + + fp->ctf_dthash = NULL; + fp->ctf_dthashlen = 0; + bzero(&fp->ctf_dtdefs, sizeof (ctf_list_t)); + + bcopy(fp, &ofp, sizeof (ctf_file_t)); + bcopy(nfp, fp, sizeof (ctf_file_t)); + bcopy(&ofp, nfp, sizeof (ctf_file_t)); + + /* + * Initialize the ctf_lookup_by_name top-level dictionary. We keep an + * array of type name prefixes and the corresponding ctf_hash to use. + * NOTE: This code must be kept in sync with the code in ctf_bufopen(). + */ + fp->ctf_lookups[0].ctl_hash = &fp->ctf_structs; + fp->ctf_lookups[1].ctl_hash = &fp->ctf_unions; + fp->ctf_lookups[2].ctl_hash = &fp->ctf_enums; + fp->ctf_lookups[3].ctl_hash = &fp->ctf_names; + + nfp->ctf_refcnt = 1; /* force nfp to be freed */ + ctf_close(nfp); + + return (0); +} + +void +ctf_dtd_insert(ctf_file_t *fp, ctf_dtdef_t *dtd) +{ + ulong_t h = dtd->dtd_type & (fp->ctf_dthashlen - 1); + + dtd->dtd_hash = fp->ctf_dthash[h]; + fp->ctf_dthash[h] = dtd; + ctf_list_append(&fp->ctf_dtdefs, dtd); +} + +void +ctf_dtd_delete(ctf_file_t *fp, ctf_dtdef_t *dtd) +{ + ulong_t h = dtd->dtd_type & (fp->ctf_dthashlen - 1); + ctf_dtdef_t *p, **q = &fp->ctf_dthash[h]; + ctf_dmdef_t *dmd, *nmd; + size_t len; + + for (p = *q; p != NULL; p = p->dtd_hash) { + if (p != dtd) + q = &p->dtd_hash; + else + break; + } + + if (p != NULL) + *q = p->dtd_hash; + + switch (CTF_INFO_KIND(dtd->dtd_data.ctt_info)) { + case CTF_K_STRUCT: + case CTF_K_UNION: + case CTF_K_ENUM: + for (dmd = ctf_list_next(&dtd->dtd_u.dtu_members); + dmd != NULL; dmd = nmd) { + if (dmd->dmd_name != NULL) { + len = strlen(dmd->dmd_name) + 1; + ctf_free(dmd->dmd_name, len); + fp->ctf_dtstrlen -= len; + } + nmd = ctf_list_next(dmd); + ctf_free(dmd, sizeof (ctf_dmdef_t)); + } + break; + case CTF_K_FUNCTION: + ctf_free(dtd->dtd_u.dtu_argv, sizeof (ctf_id_t) * + CTF_INFO_VLEN(dtd->dtd_data.ctt_info)); + break; + } + + if (dtd->dtd_name) { + len = strlen(dtd->dtd_name) + 1; + ctf_free(dtd->dtd_name, len); + fp->ctf_dtstrlen -= len; + } + + ctf_list_delete(&fp->ctf_dtdefs, dtd); + ctf_free(dtd, sizeof (ctf_dtdef_t)); +} + +ctf_dtdef_t * +ctf_dtd_lookup(ctf_file_t *fp, ctf_id_t type) +{ + ulong_t h = type & (fp->ctf_dthashlen - 1); + ctf_dtdef_t *dtd; + + if (fp->ctf_dthash == NULL) + return (NULL); + + for (dtd = fp->ctf_dthash[h]; dtd != NULL; dtd = dtd->dtd_hash) { + if (dtd->dtd_type == type) + break; + } + + return (dtd); +} + +/* + * Discard all of the dynamic type definitions that have been added to the + * container since the last call to ctf_update(). We locate such types by + * scanning the list and deleting elements that have type IDs greater than + * ctf_dtoldid, which is set by ctf_update(), above. + */ +int +ctf_discard(ctf_file_t *fp) +{ + ctf_dtdef_t *dtd, *ntd; + + if (!(fp->ctf_flags & LCTF_RDWR)) + return (ctf_set_errno(fp, ECTF_RDONLY)); + + if (!(fp->ctf_flags & LCTF_DIRTY)) + return (0); /* no update required */ + + for (dtd = ctf_list_next(&fp->ctf_dtdefs); dtd != NULL; dtd = ntd) { + if (dtd->dtd_type <= fp->ctf_dtoldid) + continue; /* skip types that have been committed */ + + ntd = ctf_list_next(dtd); + ctf_dtd_delete(fp, dtd); + } + + fp->ctf_dtnextid = fp->ctf_dtoldid + 1; + fp->ctf_flags &= ~LCTF_DIRTY; + + return (0); +} + +static ctf_id_t +ctf_add_generic(ctf_file_t *fp, uint_t flag, const char *name, ctf_dtdef_t **rp) +{ + ctf_dtdef_t *dtd; + ctf_id_t type; + char *s = NULL; + + if (flag != CTF_ADD_NONROOT && flag != CTF_ADD_ROOT) + return (ctf_set_errno(fp, EINVAL)); + + if (!(fp->ctf_flags & LCTF_RDWR)) + return (ctf_set_errno(fp, ECTF_RDONLY)); + + if (CTF_INDEX_TO_TYPE(fp->ctf_dtnextid, 1) > CTF_MAX_TYPE) + return (ctf_set_errno(fp, ECTF_FULL)); + + if ((dtd = ctf_alloc(sizeof (ctf_dtdef_t))) == NULL) + return (ctf_set_errno(fp, EAGAIN)); + + if (name != NULL && (s = ctf_strdup(name)) == NULL) { + ctf_free(dtd, sizeof (ctf_dtdef_t)); + return (ctf_set_errno(fp, EAGAIN)); + } + + type = fp->ctf_dtnextid++; + type = CTF_INDEX_TO_TYPE(type, (fp->ctf_flags & LCTF_CHILD)); + + bzero(dtd, sizeof (ctf_dtdef_t)); + dtd->dtd_name = s; + dtd->dtd_type = type; + + if (s != NULL) + fp->ctf_dtstrlen += strlen(s) + 1; + + ctf_dtd_insert(fp, dtd); + fp->ctf_flags |= LCTF_DIRTY; + + *rp = dtd; + return (type); +} + +/* + * When encoding integer sizes, we want to convert a byte count in the range + * 1-8 to the closest power of 2 (e.g. 3->4, 5->8, etc). The clp2() function + * is a clever implementation from "Hacker's Delight" by Henry Warren, Jr. + */ +static size_t +clp2(size_t x) +{ + x--; + + x |= (x >> 1); + x |= (x >> 2); + x |= (x >> 4); + x |= (x >> 8); + x |= (x >> 16); + + return (x + 1); +} + +static ctf_id_t +ctf_add_encoded(ctf_file_t *fp, uint_t flag, + const char *name, const ctf_encoding_t *ep, uint_t kind) +{ + ctf_dtdef_t *dtd; + ctf_id_t type; + + if (ep == NULL) + return (ctf_set_errno(fp, EINVAL)); + + if ((type = ctf_add_generic(fp, flag, name, &dtd)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(kind, flag, 0); + dtd->dtd_data.ctt_size = clp2(P2ROUNDUP(ep->cte_bits, NBBY) / NBBY); + dtd->dtd_u.dtu_enc = *ep; + + return (type); +} + +static ctf_id_t +ctf_add_reftype(ctf_file_t *fp, uint_t flag, ctf_id_t ref, uint_t kind) +{ + ctf_dtdef_t *dtd; + ctf_id_t type; + + if (ref == CTF_ERR || ref < 0 || ref > CTF_MAX_TYPE) + return (ctf_set_errno(fp, EINVAL)); + + if ((type = ctf_add_generic(fp, flag, NULL, &dtd)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(kind, flag, 0); + dtd->dtd_data.ctt_type = (ushort_t)ref; + + return (type); +} + +ctf_id_t +ctf_add_integer(ctf_file_t *fp, uint_t flag, + const char *name, const ctf_encoding_t *ep) +{ + return (ctf_add_encoded(fp, flag, name, ep, CTF_K_INTEGER)); +} + +ctf_id_t +ctf_add_float(ctf_file_t *fp, uint_t flag, + const char *name, const ctf_encoding_t *ep) +{ + return (ctf_add_encoded(fp, flag, name, ep, CTF_K_FLOAT)); +} + +ctf_id_t +ctf_add_pointer(ctf_file_t *fp, uint_t flag, ctf_id_t ref) +{ + return (ctf_add_reftype(fp, flag, ref, CTF_K_POINTER)); +} + +ctf_id_t +ctf_add_array(ctf_file_t *fp, uint_t flag, const ctf_arinfo_t *arp) +{ + ctf_dtdef_t *dtd; + ctf_id_t type; + + if (arp == NULL) + return (ctf_set_errno(fp, EINVAL)); + + if ((type = ctf_add_generic(fp, flag, NULL, &dtd)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(CTF_K_ARRAY, flag, 0); + dtd->dtd_data.ctt_size = 0; + dtd->dtd_u.dtu_arr = *arp; + + return (type); +} + +int +ctf_set_array(ctf_file_t *fp, ctf_id_t type, const ctf_arinfo_t *arp) +{ + ctf_dtdef_t *dtd = ctf_dtd_lookup(fp, type); + + if (!(fp->ctf_flags & LCTF_RDWR)) + return (ctf_set_errno(fp, ECTF_RDONLY)); + + if (dtd == NULL || CTF_INFO_KIND(dtd->dtd_data.ctt_info) != CTF_K_ARRAY) + return (ctf_set_errno(fp, ECTF_BADID)); + + fp->ctf_flags |= LCTF_DIRTY; + dtd->dtd_u.dtu_arr = *arp; + + return (0); +} + +ctf_id_t +ctf_add_function(ctf_file_t *fp, uint_t flag, + const ctf_funcinfo_t *ctc, const ctf_id_t *argv) +{ + ctf_dtdef_t *dtd; + ctf_id_t type; + uint_t vlen; + ctf_id_t *vdat = NULL; + + if (ctc == NULL || (ctc->ctc_flags & ~CTF_FUNC_VARARG) != 0 || + (ctc->ctc_argc != 0 && argv == NULL)) + return (ctf_set_errno(fp, EINVAL)); + + vlen = ctc->ctc_argc; + if (ctc->ctc_flags & CTF_FUNC_VARARG) + vlen++; /* add trailing zero to indicate varargs (see below) */ + + if (vlen > CTF_MAX_VLEN) + return (ctf_set_errno(fp, EOVERFLOW)); + + if (vlen != 0 && (vdat = ctf_alloc(sizeof (ctf_id_t) * vlen)) == NULL) + return (ctf_set_errno(fp, EAGAIN)); + + if ((type = ctf_add_generic(fp, flag, NULL, &dtd)) == CTF_ERR) { + ctf_free(vdat, sizeof (ctf_id_t) * vlen); + return (CTF_ERR); /* errno is set for us */ + } + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(CTF_K_FUNCTION, flag, vlen); + dtd->dtd_data.ctt_type = (ushort_t)ctc->ctc_return; + + bcopy(argv, vdat, sizeof (ctf_id_t) * ctc->ctc_argc); + if (ctc->ctc_flags & CTF_FUNC_VARARG) + vdat[vlen - 1] = 0; /* add trailing zero to indicate varargs */ + dtd->dtd_u.dtu_argv = vdat; + + return (type); +} + +ctf_id_t +ctf_add_struct(ctf_file_t *fp, uint_t flag, const char *name) +{ + ctf_hash_t *hp = &fp->ctf_structs; + ctf_helem_t *hep = NULL; + ctf_dtdef_t *dtd; + ctf_id_t type; + + if (name != NULL) + hep = ctf_hash_lookup(hp, fp, name, strlen(name)); + + if (hep != NULL && ctf_type_kind(fp, hep->h_type) == CTF_K_FORWARD) + dtd = ctf_dtd_lookup(fp, type = hep->h_type); + else if ((type = ctf_add_generic(fp, flag, name, &dtd)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(CTF_K_STRUCT, flag, 0); + dtd->dtd_data.ctt_size = 0; + + return (type); +} + +ctf_id_t +ctf_add_union(ctf_file_t *fp, uint_t flag, const char *name) +{ + ctf_hash_t *hp = &fp->ctf_unions; + ctf_helem_t *hep = NULL; + ctf_dtdef_t *dtd; + ctf_id_t type; + + if (name != NULL) + hep = ctf_hash_lookup(hp, fp, name, strlen(name)); + + if (hep != NULL && ctf_type_kind(fp, hep->h_type) == CTF_K_FORWARD) + dtd = ctf_dtd_lookup(fp, type = hep->h_type); + else if ((type = ctf_add_generic(fp, flag, name, &dtd)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(CTF_K_UNION, flag, 0); + dtd->dtd_data.ctt_size = 0; + + return (type); +} + +ctf_id_t +ctf_add_enum(ctf_file_t *fp, uint_t flag, const char *name) +{ + ctf_hash_t *hp = &fp->ctf_enums; + ctf_helem_t *hep = NULL; + ctf_dtdef_t *dtd; + ctf_id_t type; + + if (name != NULL) + hep = ctf_hash_lookup(hp, fp, name, strlen(name)); + + if (hep != NULL && ctf_type_kind(fp, hep->h_type) == CTF_K_FORWARD) + dtd = ctf_dtd_lookup(fp, type = hep->h_type); + else if ((type = ctf_add_generic(fp, flag, name, &dtd)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(CTF_K_ENUM, flag, 0); + dtd->dtd_data.ctt_size = fp->ctf_dmodel->ctd_int; + + return (type); +} + +ctf_id_t +ctf_add_forward(ctf_file_t *fp, uint_t flag, const char *name, uint_t kind) +{ + ctf_hash_t *hp; + ctf_helem_t *hep; + ctf_dtdef_t *dtd; + ctf_id_t type; + + switch (kind) { + case CTF_K_STRUCT: + hp = &fp->ctf_structs; + break; + case CTF_K_UNION: + hp = &fp->ctf_unions; + break; + case CTF_K_ENUM: + hp = &fp->ctf_enums; + break; + default: + return (ctf_set_errno(fp, ECTF_NOTSUE)); + } + + /* + * If the type is already defined or exists as a forward tag, just + * return the ctf_id_t of the existing definition. + */ + if (name != NULL && (hep = ctf_hash_lookup(hp, + fp, name, strlen(name))) != NULL) + return (hep->h_type); + + if ((type = ctf_add_generic(fp, flag, name, &dtd)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(CTF_K_FORWARD, flag, 0); + dtd->dtd_data.ctt_type = kind; + + return (type); +} + +ctf_id_t +ctf_add_typedef(ctf_file_t *fp, uint_t flag, const char *name, ctf_id_t ref) +{ + ctf_dtdef_t *dtd; + ctf_id_t type; + + if (ref == CTF_ERR || ref < 0 || ref > CTF_MAX_TYPE) + return (ctf_set_errno(fp, EINVAL)); + + if ((type = ctf_add_generic(fp, flag, name, &dtd)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(CTF_K_TYPEDEF, flag, 0); + dtd->dtd_data.ctt_type = (ushort_t)ref; + + return (type); +} + +ctf_id_t +ctf_add_volatile(ctf_file_t *fp, uint_t flag, ctf_id_t ref) +{ + return (ctf_add_reftype(fp, flag, ref, CTF_K_VOLATILE)); +} + +ctf_id_t +ctf_add_const(ctf_file_t *fp, uint_t flag, ctf_id_t ref) +{ + return (ctf_add_reftype(fp, flag, ref, CTF_K_CONST)); +} + +ctf_id_t +ctf_add_restrict(ctf_file_t *fp, uint_t flag, ctf_id_t ref) +{ + return (ctf_add_reftype(fp, flag, ref, CTF_K_RESTRICT)); +} + +int +ctf_add_enumerator(ctf_file_t *fp, ctf_id_t enid, const char *name, int value) +{ + ctf_dtdef_t *dtd = ctf_dtd_lookup(fp, enid); + ctf_dmdef_t *dmd; + + uint_t kind, vlen, root; + char *s; + + if (name == NULL) + return (ctf_set_errno(fp, EINVAL)); + + if (!(fp->ctf_flags & LCTF_RDWR)) + return (ctf_set_errno(fp, ECTF_RDONLY)); + + if (dtd == NULL) + return (ctf_set_errno(fp, ECTF_BADID)); + + kind = CTF_INFO_KIND(dtd->dtd_data.ctt_info); + root = CTF_INFO_ISROOT(dtd->dtd_data.ctt_info); + vlen = CTF_INFO_VLEN(dtd->dtd_data.ctt_info); + + if (kind != CTF_K_ENUM) + return (ctf_set_errno(fp, ECTF_NOTENUM)); + + if (vlen == CTF_MAX_VLEN) + return (ctf_set_errno(fp, ECTF_DTFULL)); + + for (dmd = ctf_list_next(&dtd->dtd_u.dtu_members); + dmd != NULL; dmd = ctf_list_next(dmd)) { + if (strcmp(dmd->dmd_name, name) == 0) + return (ctf_set_errno(fp, ECTF_DUPMEMBER)); + } + + if ((dmd = ctf_alloc(sizeof (ctf_dmdef_t))) == NULL) + return (ctf_set_errno(fp, EAGAIN)); + + if ((s = ctf_strdup(name)) == NULL) { + ctf_free(dmd, sizeof (ctf_dmdef_t)); + return (ctf_set_errno(fp, EAGAIN)); + } + + dmd->dmd_name = s; + dmd->dmd_type = CTF_ERR; + dmd->dmd_offset = 0; + dmd->dmd_value = value; + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(kind, root, vlen + 1); + ctf_list_append(&dtd->dtd_u.dtu_members, dmd); + + fp->ctf_dtstrlen += strlen(s) + 1; + fp->ctf_flags |= LCTF_DIRTY; + + return (0); +} + +int +ctf_add_member(ctf_file_t *fp, ctf_id_t souid, const char *name, ctf_id_t type) +{ + ctf_dtdef_t *dtd = ctf_dtd_lookup(fp, souid); + ctf_dmdef_t *dmd; + + ssize_t msize, malign, ssize; + uint_t kind, vlen, root; + char *s = NULL; + + if (!(fp->ctf_flags & LCTF_RDWR)) + return (ctf_set_errno(fp, ECTF_RDONLY)); + + if (dtd == NULL) + return (ctf_set_errno(fp, ECTF_BADID)); + + kind = CTF_INFO_KIND(dtd->dtd_data.ctt_info); + root = CTF_INFO_ISROOT(dtd->dtd_data.ctt_info); + vlen = CTF_INFO_VLEN(dtd->dtd_data.ctt_info); + + if (kind != CTF_K_STRUCT && kind != CTF_K_UNION) + return (ctf_set_errno(fp, ECTF_NOTSOU)); + + if (vlen == CTF_MAX_VLEN) + return (ctf_set_errno(fp, ECTF_DTFULL)); + + if (name != NULL) { + for (dmd = ctf_list_next(&dtd->dtd_u.dtu_members); + dmd != NULL; dmd = ctf_list_next(dmd)) { + if (dmd->dmd_name != NULL && + strcmp(dmd->dmd_name, name) == 0) + return (ctf_set_errno(fp, ECTF_DUPMEMBER)); + } + } + + if ((msize = ctf_type_size(fp, type)) == CTF_ERR || + (malign = ctf_type_align(fp, type)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + if ((dmd = ctf_alloc(sizeof (ctf_dmdef_t))) == NULL) + return (ctf_set_errno(fp, EAGAIN)); + + if (name != NULL && (s = ctf_strdup(name)) == NULL) { + ctf_free(dmd, sizeof (ctf_dmdef_t)); + return (ctf_set_errno(fp, EAGAIN)); + } + + dmd->dmd_name = s; + dmd->dmd_type = type; + dmd->dmd_value = -1; + + if (kind == CTF_K_STRUCT && vlen != 0) { + ctf_dmdef_t *lmd = ctf_list_prev(&dtd->dtd_u.dtu_members); + ctf_id_t ltype = ctf_type_resolve(fp, lmd->dmd_type); + size_t off = lmd->dmd_offset; + + ctf_encoding_t linfo; + ssize_t lsize; + + if (ctf_type_encoding(fp, ltype, &linfo) != CTF_ERR) + off += linfo.cte_bits; + else if ((lsize = ctf_type_size(fp, ltype)) != CTF_ERR) + off += lsize * NBBY; + + /* + * Round up the offset of the end of the last member to the + * next byte boundary, convert 'off' to bytes, and then round + * it up again to the next multiple of the alignment required + * by the new member. Finally, convert back to bits and store + * the result in dmd_offset. Technically we could do more + * efficient packing if the new member is a bit-field, but + * we're the "compiler" and ANSI says we can do as we choose. + */ + off = roundup(off, NBBY) / NBBY; + off = roundup(off, MAX(malign, 1)); + dmd->dmd_offset = off * NBBY; + ssize = off + msize; + } else { + dmd->dmd_offset = 0; + ssize = ctf_get_ctt_size(fp, &dtd->dtd_data, NULL, NULL); + ssize = MAX(ssize, msize); + } + + if (ssize > CTF_MAX_SIZE) { + dtd->dtd_data.ctt_size = CTF_LSIZE_SENT; + dtd->dtd_data.ctt_lsizehi = CTF_SIZE_TO_LSIZE_HI(ssize); + dtd->dtd_data.ctt_lsizelo = CTF_SIZE_TO_LSIZE_LO(ssize); + } else + dtd->dtd_data.ctt_size = (ushort_t)ssize; + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(kind, root, vlen + 1); + ctf_list_append(&dtd->dtd_u.dtu_members, dmd); + + if (s != NULL) + fp->ctf_dtstrlen += strlen(s) + 1; + + fp->ctf_flags |= LCTF_DIRTY; + return (0); +} + +static int +enumcmp(const char *name, int value, void *arg) +{ + ctf_bundle_t *ctb = arg; + int bvalue; + + return (ctf_enum_value(ctb->ctb_file, ctb->ctb_type, + name, &bvalue) == CTF_ERR || value != bvalue); +} + +static int +enumadd(const char *name, int value, void *arg) +{ + ctf_bundle_t *ctb = arg; + + return (ctf_add_enumerator(ctb->ctb_file, ctb->ctb_type, + name, value) == CTF_ERR); +} + +/*ARGSUSED*/ +static int +membcmp(const char *name, ctf_id_t type, ulong_t offset, void *arg) +{ + ctf_bundle_t *ctb = arg; + ctf_membinfo_t ctm; + + return (ctf_member_info(ctb->ctb_file, ctb->ctb_type, + name, &ctm) == CTF_ERR || ctm.ctm_offset != offset); +} + +static int +membadd(const char *name, ctf_id_t type, ulong_t offset, void *arg) +{ + ctf_bundle_t *ctb = arg; + ctf_dmdef_t *dmd; + char *s = NULL; + + if ((dmd = ctf_alloc(sizeof (ctf_dmdef_t))) == NULL) + return (ctf_set_errno(ctb->ctb_file, EAGAIN)); + + if (name != NULL && (s = ctf_strdup(name)) == NULL) { + ctf_free(dmd, sizeof (ctf_dmdef_t)); + return (ctf_set_errno(ctb->ctb_file, EAGAIN)); + } + + /* + * For now, dmd_type is copied as the src_fp's type; it is reset to an + * equivalent dst_fp type by a final loop in ctf_add_type(), below. + */ + dmd->dmd_name = s; + dmd->dmd_type = type; + dmd->dmd_offset = offset; + dmd->dmd_value = -1; + + ctf_list_append(&ctb->ctb_dtd->dtd_u.dtu_members, dmd); + + if (s != NULL) + ctb->ctb_file->ctf_dtstrlen += strlen(s) + 1; + + ctb->ctb_file->ctf_flags |= LCTF_DIRTY; + return (0); +} + +/* + * The ctf_add_type routine is used to copy a type from a source CTF container + * to a dynamic destination container. This routine operates recursively by + * following the source type's links and embedded member types. If the + * destination container already contains a named type which has the same + * attributes, then we succeed and return this type but no changes occur. + */ +ctf_id_t +ctf_add_type(ctf_file_t *dst_fp, ctf_file_t *src_fp, ctf_id_t src_type) +{ + ctf_id_t dst_type = CTF_ERR; + uint_t dst_kind = CTF_K_UNKNOWN; + + const ctf_type_t *tp; + const char *name; + uint_t kind, flag, vlen; + + ctf_bundle_t src, dst; + ctf_encoding_t src_en, dst_en; + ctf_arinfo_t src_ar, dst_ar; + + ctf_dtdef_t *dtd; + ctf_funcinfo_t ctc; + ssize_t size; + + ctf_hash_t *hp; + ctf_helem_t *hep; + + if (!(dst_fp->ctf_flags & LCTF_RDWR)) + return (ctf_set_errno(dst_fp, ECTF_RDONLY)); + + if ((tp = ctf_lookup_by_id(&src_fp, src_type)) == NULL) + return (ctf_set_errno(dst_fp, ctf_errno(src_fp))); + + name = ctf_strptr(src_fp, tp->ctt_name); + kind = LCTF_INFO_KIND(src_fp, tp->ctt_info); + flag = LCTF_INFO_ROOT(src_fp, tp->ctt_info); + vlen = LCTF_INFO_VLEN(src_fp, tp->ctt_info); + + switch (kind) { + case CTF_K_STRUCT: + hp = &dst_fp->ctf_structs; + break; + case CTF_K_UNION: + hp = &dst_fp->ctf_unions; + break; + case CTF_K_ENUM: + hp = &dst_fp->ctf_enums; + break; + default: + hp = &dst_fp->ctf_names; + break; + } + + /* + * If the source type has a name and is a root type (visible at the + * top-level scope), lookup the name in the destination container and + * verify that it is of the same kind before we do anything else. + */ + if ((flag & CTF_ADD_ROOT) && name[0] != '\0' && + (hep = ctf_hash_lookup(hp, dst_fp, name, strlen(name))) != NULL) { + dst_type = (ctf_id_t)hep->h_type; + dst_kind = ctf_type_kind(dst_fp, dst_type); + } + + /* + * If an identically named dst_type exists, fail with ECTF_CONFLICT + * unless dst_type is a forward declaration and src_type is a struct, + * union, or enum (i.e. the definition of the previous forward decl). + */ + if (dst_type != CTF_ERR && dst_kind != kind && ( + dst_kind != CTF_K_FORWARD || (kind != CTF_K_ENUM && + kind != CTF_K_STRUCT && kind != CTF_K_UNION))) + return (ctf_set_errno(dst_fp, ECTF_CONFLICT)); + + /* + * If the non-empty name was not found in the appropriate hash, search + * the list of pending dynamic definitions that are not yet committed. + * If a matching name and kind are found, assume this is the type that + * we are looking for. This is necessary to permit ctf_add_type() to + * operate recursively on entities such as a struct that contains a + * pointer member that refers to the same struct type. + */ + if (dst_type == CTF_ERR && name[0] != '\0') { + for (dtd = ctf_list_prev(&dst_fp->ctf_dtdefs); dtd != NULL && + dtd->dtd_type > dst_fp->ctf_dtoldid; + dtd = ctf_list_prev(dtd)) { + if (CTF_INFO_KIND(dtd->dtd_data.ctt_info) == kind && + dtd->dtd_name != NULL && + strcmp(dtd->dtd_name, name) == 0) + return (dtd->dtd_type); + } + } + + src.ctb_file = src_fp; + src.ctb_type = src_type; + src.ctb_dtd = NULL; + + dst.ctb_file = dst_fp; + dst.ctb_type = dst_type; + dst.ctb_dtd = NULL; + + /* + * Now perform kind-specific processing. If dst_type is CTF_ERR, then + * we add a new type with the same properties as src_type to dst_fp. + * If dst_type is not CTF_ERR, then we verify that dst_type has the + * same attributes as src_type. We recurse for embedded references. + */ + switch (kind) { + case CTF_K_INTEGER: + case CTF_K_FLOAT: + if (ctf_type_encoding(src_fp, src_type, &src_en) != 0) + return (ctf_set_errno(dst_fp, ctf_errno(src_fp))); + + if (dst_type != CTF_ERR) { + if (ctf_type_encoding(dst_fp, dst_type, &dst_en) != 0) + return (CTF_ERR); /* errno is set for us */ + + if (bcmp(&src_en, &dst_en, sizeof (ctf_encoding_t))) + return (ctf_set_errno(dst_fp, ECTF_CONFLICT)); + + } else if (kind == CTF_K_INTEGER) { + dst_type = ctf_add_integer(dst_fp, flag, name, &src_en); + } else + dst_type = ctf_add_float(dst_fp, flag, name, &src_en); + break; + + case CTF_K_POINTER: + case CTF_K_VOLATILE: + case CTF_K_CONST: + case CTF_K_RESTRICT: + src_type = ctf_type_reference(src_fp, src_type); + src_type = ctf_add_type(dst_fp, src_fp, src_type); + + if (src_type == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dst_type = ctf_add_reftype(dst_fp, flag, src_type, kind); + break; + + case CTF_K_ARRAY: + if (ctf_array_info(src_fp, src_type, &src_ar) == CTF_ERR) + return (ctf_set_errno(dst_fp, ctf_errno(src_fp))); + + src_ar.ctr_contents = + ctf_add_type(dst_fp, src_fp, src_ar.ctr_contents); + src_ar.ctr_index = + ctf_add_type(dst_fp, src_fp, src_ar.ctr_index); + src_ar.ctr_nelems = src_ar.ctr_nelems; + + if (src_ar.ctr_contents == CTF_ERR || + src_ar.ctr_index == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + if (dst_type != CTF_ERR) { + if (ctf_array_info(dst_fp, dst_type, &dst_ar) != 0) + return (CTF_ERR); /* errno is set for us */ + + if (bcmp(&src_ar, &dst_ar, sizeof (ctf_arinfo_t))) + return (ctf_set_errno(dst_fp, ECTF_CONFLICT)); + } else + dst_type = ctf_add_array(dst_fp, flag, &src_ar); + break; + + case CTF_K_FUNCTION: + ctc.ctc_return = ctf_add_type(dst_fp, src_fp, tp->ctt_type); + ctc.ctc_argc = 0; + ctc.ctc_flags = 0; + + if (ctc.ctc_return == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dst_type = ctf_add_function(dst_fp, flag, &ctc, NULL); + break; + + case CTF_K_STRUCT: + case CTF_K_UNION: { + ctf_dmdef_t *dmd; + int errs = 0; + + /* + * Technically to match a struct or union we need to check both + * ways (src members vs. dst, dst members vs. src) but we make + * this more optimal by only checking src vs. dst and comparing + * the total size of the structure (which we must do anyway) + * which covers the possibility of dst members not in src. + * This optimization can be defeated for unions, but is so + * pathological as to render it irrelevant for our purposes. + */ + if (dst_type != CTF_ERR && dst_kind != CTF_K_FORWARD) { + if (ctf_type_size(src_fp, src_type) != + ctf_type_size(dst_fp, dst_type)) + return (ctf_set_errno(dst_fp, ECTF_CONFLICT)); + + if (ctf_member_iter(src_fp, src_type, membcmp, &dst)) + return (ctf_set_errno(dst_fp, ECTF_CONFLICT)); + + break; + } + + /* + * Unlike the other cases, copying structs and unions is done + * manually so as to avoid repeated lookups in ctf_add_member + * and to ensure the exact same member offsets as in src_type. + */ + dst_type = ctf_add_generic(dst_fp, flag, name, &dtd); + if (dst_type == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + dst.ctb_type = dst_type; + dst.ctb_dtd = dtd; + + if (ctf_member_iter(src_fp, src_type, membadd, &dst) != 0) + errs++; /* increment errs and fail at bottom of case */ + + if ((size = ctf_type_size(src_fp, src_type)) > CTF_MAX_SIZE) { + dtd->dtd_data.ctt_size = CTF_LSIZE_SENT; + dtd->dtd_data.ctt_lsizehi = CTF_SIZE_TO_LSIZE_HI(size); + dtd->dtd_data.ctt_lsizelo = CTF_SIZE_TO_LSIZE_LO(size); + } else + dtd->dtd_data.ctt_size = (ushort_t)size; + + dtd->dtd_data.ctt_info = CTF_TYPE_INFO(kind, flag, vlen); + + /* + * Make a final pass through the members changing each dmd_type + * (a src_fp type) to an equivalent type in dst_fp. We pass + * through all members, leaving any that fail set to CTF_ERR. + */ + for (dmd = ctf_list_next(&dtd->dtd_u.dtu_members); + dmd != NULL; dmd = ctf_list_next(dmd)) { + if ((dmd->dmd_type = ctf_add_type(dst_fp, src_fp, + dmd->dmd_type)) == CTF_ERR) + errs++; + } + + if (errs) + return (CTF_ERR); /* errno is set for us */ + break; + } + + case CTF_K_ENUM: + if (dst_type != CTF_ERR && dst_kind != CTF_K_FORWARD) { + if (ctf_enum_iter(src_fp, src_type, enumcmp, &dst) || + ctf_enum_iter(dst_fp, dst_type, enumcmp, &src)) + return (ctf_set_errno(dst_fp, ECTF_CONFLICT)); + } else { + dst_type = ctf_add_enum(dst_fp, flag, name); + if ((dst.ctb_type = dst_type) == CTF_ERR || + ctf_enum_iter(src_fp, src_type, enumadd, &dst)) + return (CTF_ERR); /* errno is set for us */ + } + break; + + case CTF_K_FORWARD: + if (dst_type == CTF_ERR) { + dst_type = ctf_add_forward(dst_fp, + flag, name, CTF_K_STRUCT); /* assume STRUCT */ + } + break; + + case CTF_K_TYPEDEF: + src_type = ctf_type_reference(src_fp, src_type); + src_type = ctf_add_type(dst_fp, src_fp, src_type); + + if (src_type == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + /* + * If dst_type is not CTF_ERR at this point, we should check if + * ctf_type_reference(dst_fp, dst_type) != src_type and if so + * fail with ECTF_CONFLICT. However, this causes problems with + * <sys/types.h> typedefs that vary based on things like if + * _ILP32x then pid_t is int otherwise long. We therefore omit + * this check and assume that if the identically named typedef + * already exists in dst_fp, it is correct or equivalent. + */ + if (dst_type == CTF_ERR) { + dst_type = ctf_add_typedef(dst_fp, flag, + name, src_type); + } + break; + + default: + return (ctf_set_errno(dst_fp, ECTF_CORRUPT)); + } + + return (dst_type); +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_decl.c b/cddl/contrib/opensolaris/common/ctf/ctf_decl.c new file mode 100644 index 0000000..6bf5700 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_decl.c @@ -0,0 +1,184 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2005 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +/* + * CTF Declaration Stack + * + * In order to implement ctf_type_name(), we must convert a type graph back + * into a C type declaration. Unfortunately, a type graph represents a storage + * class ordering of the type whereas a type declaration must obey the C rules + * for operator precedence, and the two orderings are frequently in conflict. + * For example, consider these CTF type graphs and their C declarations: + * + * CTF_K_POINTER -> CTF_K_FUNCTION -> CTF_K_INTEGER : int (*)() + * CTF_K_POINTER -> CTF_K_ARRAY -> CTF_K_INTEGER : int (*)[] + * + * In each case, parentheses are used to raise operator * to higher lexical + * precedence, so the string form of the C declaration cannot be constructed by + * walking the type graph links and forming the string from left to right. + * + * The functions in this file build a set of stacks from the type graph nodes + * corresponding to the C operator precedence levels in the appropriate order. + * The code in ctf_type_name() can then iterate over the levels and nodes in + * lexical precedence order and construct the final C declaration string. + */ + +#include <ctf_impl.h> + +void +ctf_decl_init(ctf_decl_t *cd, char *buf, size_t len) +{ + int i; + + bzero(cd, sizeof (ctf_decl_t)); + + for (i = CTF_PREC_BASE; i < CTF_PREC_MAX; i++) + cd->cd_order[i] = CTF_PREC_BASE - 1; + + cd->cd_qualp = CTF_PREC_BASE; + cd->cd_ordp = CTF_PREC_BASE; + + cd->cd_buf = buf; + cd->cd_ptr = buf; + cd->cd_end = buf + len; +} + +void +ctf_decl_fini(ctf_decl_t *cd) +{ + ctf_decl_node_t *cdp, *ndp; + int i; + + for (i = CTF_PREC_BASE; i < CTF_PREC_MAX; i++) { + for (cdp = ctf_list_next(&cd->cd_nodes[i]); + cdp != NULL; cdp = ndp) { + ndp = ctf_list_next(cdp); + ctf_free(cdp, sizeof (ctf_decl_node_t)); + } + } +} + +void +ctf_decl_push(ctf_decl_t *cd, ctf_file_t *fp, ctf_id_t type) +{ + ctf_decl_node_t *cdp; + ctf_decl_prec_t prec; + uint_t kind, n = 1; + int is_qual = 0; + + const ctf_type_t *tp; + ctf_arinfo_t ar; + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) { + cd->cd_err = fp->ctf_errno; + return; + } + + switch (kind = LCTF_INFO_KIND(fp, tp->ctt_info)) { + case CTF_K_ARRAY: + (void) ctf_array_info(fp, type, &ar); + ctf_decl_push(cd, fp, ar.ctr_contents); + n = ar.ctr_nelems; + prec = CTF_PREC_ARRAY; + break; + + case CTF_K_TYPEDEF: + if (ctf_strptr(fp, tp->ctt_name)[0] == '\0') { + ctf_decl_push(cd, fp, tp->ctt_type); + return; + } + prec = CTF_PREC_BASE; + break; + + case CTF_K_FUNCTION: + ctf_decl_push(cd, fp, tp->ctt_type); + prec = CTF_PREC_FUNCTION; + break; + + case CTF_K_POINTER: + ctf_decl_push(cd, fp, tp->ctt_type); + prec = CTF_PREC_POINTER; + break; + + case CTF_K_VOLATILE: + case CTF_K_CONST: + case CTF_K_RESTRICT: + ctf_decl_push(cd, fp, tp->ctt_type); + prec = cd->cd_qualp; + is_qual++; + break; + + default: + prec = CTF_PREC_BASE; + } + + if ((cdp = ctf_alloc(sizeof (ctf_decl_node_t))) == NULL) { + cd->cd_err = EAGAIN; + return; + } + + cdp->cd_type = type; + cdp->cd_kind = kind; + cdp->cd_n = n; + + if (ctf_list_next(&cd->cd_nodes[prec]) == NULL) + cd->cd_order[prec] = cd->cd_ordp++; + + /* + * Reset cd_qualp to the highest precedence level that we've seen so + * far that can be qualified (CTF_PREC_BASE or CTF_PREC_POINTER). + */ + if (prec > cd->cd_qualp && prec < CTF_PREC_ARRAY) + cd->cd_qualp = prec; + + /* + * C array declarators are ordered inside out so prepend them. Also by + * convention qualifiers of base types precede the type specifier (e.g. + * const int vs. int const) even though the two forms are equivalent. + */ + if (kind == CTF_K_ARRAY || (is_qual && prec == CTF_PREC_BASE)) + ctf_list_prepend(&cd->cd_nodes[prec], cdp); + else + ctf_list_append(&cd->cd_nodes[prec], cdp); +} + +/*PRINTFLIKE2*/ +void +ctf_decl_sprintf(ctf_decl_t *cd, const char *format, ...) +{ + size_t len = (size_t)(cd->cd_end - cd->cd_ptr); + va_list ap; + size_t n; + + va_start(ap, format); + n = vsnprintf(cd->cd_ptr, len, format, ap); + va_end(ap); + + cd->cd_ptr += MIN(n, len); + cd->cd_len += n; +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_error.c b/cddl/contrib/opensolaris/common/ctf/ctf_error.c new file mode 100644 index 0000000..888c6c8 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_error.c @@ -0,0 +1,97 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2003 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <ctf_impl.h> + +static const char *const _ctf_errlist[] = { + "File is not in CTF or ELF format", /* ECTF_FMT */ + "File uses more recent ELF version than libctf", /* ECTF_ELFVERS */ + "File uses more recent CTF version than libctf", /* ECTF_CTFVERS */ + "File is a different endian-ness than libctf", /* ECTF_ENDIAN */ + "Symbol table uses invalid entry size", /* ECTF_SYMTAB */ + "Symbol table data buffer is not valid", /* ECTF_SYMBAD */ + "String table data buffer is not valid", /* ECTF_STRBAD */ + "File data structure corruption detected", /* ECTF_CORRUPT */ + "File does not contain CTF data", /* ECTF_NOCTFDATA */ + "Buffer does not contain CTF data", /* ECTF_NOCTFBUF */ + "Symbol table information is not available", /* ECTF_NOSYMTAB */ + "Type information is in parent and unavailable", /* ECTF_NOPARENT */ + "Cannot import types with different data model", /* ECTF_DMODEL */ + "Failed to mmap a needed data section", /* ECTF_MMAP */ + "Decompression package SUNWzlib not installed", /* ECTF_ZMISSING */ + "Failed to initialize decompression library", /* ECTF_ZINIT */ + "Failed to allocate decompression buffer", /* ECTF_ZALLOC */ + "Failed to decompress CTF data", /* ECTF_DECOMPRESS */ + "External string table is not available", /* ECTF_STRTAB */ + "String name offset is corrupt", /* ECTF_BADNAME */ + "Invalid type identifier", /* ECTF_BADID */ + "Type is not a struct or union", /* ECTF_NOTSOU */ + "Type is not an enum", /* ECTF_NOTENUM */ + "Type is not a struct, union, or enum", /* ECTF_NOTSUE */ + "Type is not an integer or float", /* ECTF_NOTINTFP */ + "Type is not an array", /* ECTF_NOTARRAY */ + "Type does not reference another type", /* ECTF_NOTREF */ + "Input buffer is too small for type name", /* ECTF_NAMELEN */ + "No type information available for that name", /* ECTF_NOTYPE */ + "Syntax error in type name", /* ECTF_SYNTAX */ + "Symbol table entry is not a function", /* ECTF_NOTFUNC */ + "No function information available for symbol", /* ECTF_NOFUNCDAT */ + "Symbol table entry is not a data object", /* ECTF_NOTDATA */ + "No type information available for symbol", /* ECTF_NOTYPEDAT */ + "No label information available for that name", /* ECTF_NOLABEL */ + "File does not contain any labels", /* ECTF_NOLABELDATA */ + "Feature not supported", /* ECTF_NOTSUP */ + "Invalid enum element name", /* ECTF_NOENUMNAM */ + "Invalid member name", /* ECTF_NOMEMBNAM */ + "CTF container is read-only", /* ECTF_RDONLY */ + "Limit on number of dynamic type members reached", /* ECTF_DTFULL */ + "Limit on number of dynamic types reached", /* ECTF_FULL */ + "Duplicate member name definition", /* ECTF_DUPMEMBER */ + "Conflicting type is already defined", /* ECTF_CONFLICT */ +}; + +static const int _ctf_nerr = sizeof (_ctf_errlist) / sizeof (_ctf_errlist[0]); + +const char * +ctf_errmsg(int error) +{ + const char *str; + + if (error >= ECTF_BASE && (error - ECTF_BASE) < _ctf_nerr) + str = _ctf_errlist[error - ECTF_BASE]; + else + str = ctf_strerror(error); + + return (str ? str : "Unknown error"); +} + +int +ctf_errno(ctf_file_t *fp) +{ + return (fp->ctf_errno); +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_hash.c b/cddl/contrib/opensolaris/common/ctf/ctf_hash.c new file mode 100644 index 0000000..b10a761 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_hash.c @@ -0,0 +1,178 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2006 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <ctf_impl.h> + +static const ushort_t _CTF_EMPTY[1] = { 0 }; + +int +ctf_hash_create(ctf_hash_t *hp, ulong_t nelems) +{ + if (nelems > USHRT_MAX) + return (EOVERFLOW); + + /* + * If the hash table is going to be empty, don't bother allocating any + * memory and make the only bucket point to a zero so lookups fail. + */ + if (nelems == 0) { + bzero(hp, sizeof (ctf_hash_t)); + hp->h_buckets = (ushort_t *)_CTF_EMPTY; + hp->h_nbuckets = 1; + return (0); + } + + hp->h_nbuckets = 211; /* use a prime number of hash buckets */ + hp->h_nelems = nelems + 1; /* we use index zero as a sentinel */ + hp->h_free = 1; /* first free element is index 1 */ + + hp->h_buckets = ctf_alloc(sizeof (ushort_t) * hp->h_nbuckets); + hp->h_chains = ctf_alloc(sizeof (ctf_helem_t) * hp->h_nelems); + + if (hp->h_buckets == NULL || hp->h_chains == NULL) { + ctf_hash_destroy(hp); + return (EAGAIN); + } + + bzero(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); + bzero(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); + + return (0); +} + +uint_t +ctf_hash_size(const ctf_hash_t *hp) +{ + return (hp->h_nelems ? hp->h_nelems - 1 : 0); +} + +static ulong_t +ctf_hash_compute(const char *key, size_t len) +{ + ulong_t g, h = 0; + const char *p, *q = key + len; + size_t n = 0; + + for (p = key; p < q; p++, n++) { + h = (h << 4) + *p; + + if ((g = (h & 0xf0000000)) != 0) { + h ^= (g >> 24); + h ^= g; + } + } + + return (h); +} + +int +ctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) +{ + ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID(name)]; + const char *str = ctsp->cts_strs + CTF_NAME_OFFSET(name); + ctf_helem_t *hep = &hp->h_chains[hp->h_free]; + ulong_t h; + + if (type == 0) + return (EINVAL); + + if (hp->h_free >= hp->h_nelems) + return (EOVERFLOW); + + if (ctsp->cts_strs == NULL) + return (ECTF_STRTAB); + + if (ctsp->cts_len <= CTF_NAME_OFFSET(name)) + return (ECTF_BADNAME); + + if (str[0] == '\0') + return (0); /* just ignore empty strings on behalf of caller */ + + hep->h_name = name; + hep->h_type = type; + h = ctf_hash_compute(str, strlen(str)) % hp->h_nbuckets; + hep->h_next = hp->h_buckets[h]; + hp->h_buckets[h] = hp->h_free++; + + return (0); +} + +/* + * Wrapper for ctf_hash_lookup/ctf_hash_insert: if the key is already in the + * hash, override the previous definition with this new official definition. + * If the key is not present, then call ctf_hash_insert() and hash it in. + */ +int +ctf_hash_define(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) +{ + const char *str = ctf_strptr(fp, name); + ctf_helem_t *hep = ctf_hash_lookup(hp, fp, str, strlen(str)); + + if (hep == NULL) + return (ctf_hash_insert(hp, fp, type, name)); + + hep->h_type = type; + return (0); +} + +ctf_helem_t * +ctf_hash_lookup(ctf_hash_t *hp, ctf_file_t *fp, const char *key, size_t len) +{ + ctf_helem_t *hep; + ctf_strs_t *ctsp; + const char *str; + ushort_t i; + + ulong_t h = ctf_hash_compute(key, len) % hp->h_nbuckets; + + for (i = hp->h_buckets[h]; i != 0; i = hep->h_next) { + hep = &hp->h_chains[i]; + ctsp = &fp->ctf_str[CTF_NAME_STID(hep->h_name)]; + str = ctsp->cts_strs + CTF_NAME_OFFSET(hep->h_name); + + if (strncmp(key, str, len) == 0 && str[len] == '\0') + return (hep); + } + + return (NULL); +} + +void +ctf_hash_destroy(ctf_hash_t *hp) +{ + if (hp->h_buckets != NULL && hp->h_nbuckets != 1) { + ctf_free(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); + hp->h_buckets = NULL; + } + + if (hp->h_chains != NULL) { + ctf_free(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); + hp->h_chains = NULL; + } +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_impl.h b/cddl/contrib/opensolaris/common/ctf/ctf_impl.h new file mode 100644 index 0000000..9999080 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_impl.h @@ -0,0 +1,336 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2006 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#ifndef _CTF_IMPL_H +#define _CTF_IMPL_H + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <sys/types.h> +#include <sys/errno.h> +#include <sys/sysmacros.h> +#include <sys/ctf_api.h> + +#ifdef _KERNEL + +#include <sys/systm.h> +#include <sys/cmn_err.h> +#include <sys/varargs.h> + +#define isspace(c) \ + ((c) == ' ' || (c) == '\t' || (c) == '\n' || \ + (c) == '\r' || (c) == '\f' || (c) == '\v') + +#define MAP_FAILED ((void *)-1) + +#else /* _KERNEL */ + +#include <strings.h> +#include <stdlib.h> +#include <stdarg.h> +#include <stdio.h> +#include <limits.h> +#include <ctype.h> + +#endif /* _KERNEL */ + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct ctf_helem { + uint_t h_name; /* reference to name in string table */ + ushort_t h_type; /* corresponding type ID number */ + ushort_t h_next; /* index of next element in hash chain */ +} ctf_helem_t; + +typedef struct ctf_hash { + ushort_t *h_buckets; /* hash bucket array (chain indices) */ + ctf_helem_t *h_chains; /* hash chains buffer */ + ushort_t h_nbuckets; /* number of elements in bucket array */ + ushort_t h_nelems; /* number of elements in hash table */ + uint_t h_free; /* index of next free hash element */ +} ctf_hash_t; + +typedef struct ctf_strs { + const char *cts_strs; /* base address of string table */ + size_t cts_len; /* size of string table in bytes */ +} ctf_strs_t; + +typedef struct ctf_dmodel { + const char *ctd_name; /* data model name */ + int ctd_code; /* data model code */ + size_t ctd_pointer; /* size of void * in bytes */ + size_t ctd_char; /* size of char in bytes */ + size_t ctd_short; /* size of short in bytes */ + size_t ctd_int; /* size of int in bytes */ + size_t ctd_long; /* size of long in bytes */ +} ctf_dmodel_t; + +typedef struct ctf_lookup { + const char *ctl_prefix; /* string prefix for this lookup */ + size_t ctl_len; /* length of prefix string in bytes */ + ctf_hash_t *ctl_hash; /* pointer to hash table for lookup */ +} ctf_lookup_t; + +typedef struct ctf_fileops { + ushort_t (*ctfo_get_kind)(ushort_t); + ushort_t (*ctfo_get_root)(ushort_t); + ushort_t (*ctfo_get_vlen)(ushort_t); +} ctf_fileops_t; + +typedef struct ctf_list { + struct ctf_list *l_prev; /* previous pointer or tail pointer */ + struct ctf_list *l_next; /* next pointer or head pointer */ +} ctf_list_t; + +typedef enum { + CTF_PREC_BASE, + CTF_PREC_POINTER, + CTF_PREC_ARRAY, + CTF_PREC_FUNCTION, + CTF_PREC_MAX +} ctf_decl_prec_t; + +typedef struct ctf_decl_node { + ctf_list_t cd_list; /* linked list pointers */ + ctf_id_t cd_type; /* type identifier */ + uint_t cd_kind; /* type kind */ + uint_t cd_n; /* type dimension if array */ +} ctf_decl_node_t; + +typedef struct ctf_decl { + ctf_list_t cd_nodes[CTF_PREC_MAX]; /* declaration node stacks */ + int cd_order[CTF_PREC_MAX]; /* storage order of decls */ + ctf_decl_prec_t cd_qualp; /* qualifier precision */ + ctf_decl_prec_t cd_ordp; /* ordered precision */ + char *cd_buf; /* buffer for output */ + char *cd_ptr; /* buffer location */ + char *cd_end; /* buffer limit */ + size_t cd_len; /* buffer space required */ + int cd_err; /* saved error value */ +} ctf_decl_t; + +typedef struct ctf_dmdef { + ctf_list_t dmd_list; /* list forward/back pointers */ + char *dmd_name; /* name of this member */ + ctf_id_t dmd_type; /* type of this member (for sou) */ + ulong_t dmd_offset; /* offset of this member in bits (for sou) */ + int dmd_value; /* value of this member (for enum) */ +} ctf_dmdef_t; + +typedef struct ctf_dtdef { + ctf_list_t dtd_list; /* list forward/back pointers */ + struct ctf_dtdef *dtd_hash; /* hash chain pointer for ctf_dthash */ + char *dtd_name; /* name associated with definition (if any) */ + ctf_id_t dtd_type; /* type identifier for this definition */ + ctf_type_t dtd_data; /* type node (see <sys/ctf.h>) */ + union { + ctf_list_t dtu_members; /* struct, union, or enum */ + ctf_arinfo_t dtu_arr; /* array */ + ctf_encoding_t dtu_enc; /* integer or float */ + ctf_id_t *dtu_argv; /* function */ + } dtd_u; +} ctf_dtdef_t; + +typedef struct ctf_bundle { + ctf_file_t *ctb_file; /* CTF container handle */ + ctf_id_t ctb_type; /* CTF type identifier */ + ctf_dtdef_t *ctb_dtd; /* CTF dynamic type definition (if any) */ +} ctf_bundle_t; + +/* + * The ctf_file is the structure used to represent a CTF container to library + * clients, who see it only as an opaque pointer. Modifications can therefore + * be made freely to this structure without regard to client versioning. The + * ctf_file_t typedef appears in <sys/ctf_api.h> and declares a forward tag. + * + * NOTE: ctf_update() requires that everything inside of ctf_file either be an + * immediate value, a pointer to dynamically allocated data *outside* of the + * ctf_file itself, or a pointer to statically allocated data. If you add a + * pointer to ctf_file that points to something within the ctf_file itself, + * you must make corresponding changes to ctf_update(). + */ +struct ctf_file { + const ctf_fileops_t *ctf_fileops; /* version-specific file operations */ + ctf_sect_t ctf_data; /* CTF data from object file */ + ctf_sect_t ctf_symtab; /* symbol table from object file */ + ctf_sect_t ctf_strtab; /* string table from object file */ + ctf_hash_t ctf_structs; /* hash table of struct types */ + ctf_hash_t ctf_unions; /* hash table of union types */ + ctf_hash_t ctf_enums; /* hash table of enum types */ + ctf_hash_t ctf_names; /* hash table of remaining type names */ + ctf_lookup_t ctf_lookups[5]; /* pointers to hashes for name lookup */ + ctf_strs_t ctf_str[2]; /* array of string table base and bounds */ + const uchar_t *ctf_base; /* base of CTF header + uncompressed buffer */ + const uchar_t *ctf_buf; /* uncompressed CTF data buffer */ + size_t ctf_size; /* size of CTF header + uncompressed data */ + uint_t *ctf_sxlate; /* translation table for symtab entries */ + ulong_t ctf_nsyms; /* number of entries in symtab xlate table */ + uint_t *ctf_txlate; /* translation table for type IDs */ + ushort_t *ctf_ptrtab; /* translation table for pointer-to lookups */ + ulong_t ctf_typemax; /* maximum valid type ID number */ + const ctf_dmodel_t *ctf_dmodel; /* data model pointer (see above) */ + struct ctf_file *ctf_parent; /* parent CTF container (if any) */ + const char *ctf_parlabel; /* label in parent container (if any) */ + const char *ctf_parname; /* basename of parent (if any) */ + uint_t ctf_refcnt; /* reference count (for parent links) */ + uint_t ctf_flags; /* libctf flags (see below) */ + int ctf_errno; /* error code for most recent error */ + int ctf_version; /* CTF data version */ + ctf_dtdef_t **ctf_dthash; /* hash of dynamic type definitions */ + ulong_t ctf_dthashlen; /* size of dynamic type hash bucket array */ + ctf_list_t ctf_dtdefs; /* list of dynamic type definitions */ + size_t ctf_dtstrlen; /* total length of dynamic type strings */ + ulong_t ctf_dtnextid; /* next dynamic type id to assign */ + ulong_t ctf_dtoldid; /* oldest id that has been committed */ + void *ctf_specific; /* data for ctf_get/setspecific */ +}; + +#define LCTF_INDEX_TO_TYPEPTR(fp, i) \ + ((ctf_type_t *)((uintptr_t)(fp)->ctf_buf + (fp)->ctf_txlate[(i)])) + +#define LCTF_INFO_KIND(fp, info) ((fp)->ctf_fileops->ctfo_get_kind(info)) +#define LCTF_INFO_ROOT(fp, info) ((fp)->ctf_fileops->ctfo_get_root(info)) +#define LCTF_INFO_VLEN(fp, info) ((fp)->ctf_fileops->ctfo_get_vlen(info)) + +#define LCTF_MMAP 0x0001 /* libctf should munmap buffers on close */ +#define LCTF_CHILD 0x0002 /* CTF container is a child */ +#define LCTF_RDWR 0x0004 /* CTF container is writable */ +#define LCTF_DIRTY 0x0008 /* CTF container has been modified */ + +#define ECTF_BASE 1000 /* base value for libctf errnos */ + +enum { + ECTF_FMT = ECTF_BASE, /* file is not in CTF or ELF format */ + ECTF_ELFVERS, /* ELF version is more recent than libctf */ + ECTF_CTFVERS, /* CTF version is more recent than libctf */ + ECTF_ENDIAN, /* data is different endian-ness than lib */ + ECTF_SYMTAB, /* symbol table uses invalid entry size */ + ECTF_SYMBAD, /* symbol table data buffer invalid */ + ECTF_STRBAD, /* string table data buffer invalid */ + ECTF_CORRUPT, /* file data corruption detected */ + ECTF_NOCTFDATA, /* ELF file does not contain CTF data */ + ECTF_NOCTFBUF, /* buffer does not contain CTF data */ + ECTF_NOSYMTAB, /* symbol table data is not available */ + ECTF_NOPARENT, /* parent CTF container is not available */ + ECTF_DMODEL, /* data model mismatch */ + ECTF_MMAP, /* failed to mmap a data section */ + ECTF_ZMISSING, /* decompression library not installed */ + ECTF_ZINIT, /* failed to initialize decompression library */ + ECTF_ZALLOC, /* failed to allocate decompression buffer */ + ECTF_DECOMPRESS, /* failed to decompress CTF data */ + ECTF_STRTAB, /* string table for this string is missing */ + ECTF_BADNAME, /* string offset is corrupt w.r.t. strtab */ + ECTF_BADID, /* invalid type ID number */ + ECTF_NOTSOU, /* type is not a struct or union */ + ECTF_NOTENUM, /* type is not an enum */ + ECTF_NOTSUE, /* type is not a struct, union, or enum */ + ECTF_NOTINTFP, /* type is not an integer or float */ + ECTF_NOTARRAY, /* type is not an array */ + ECTF_NOTREF, /* type does not reference another type */ + ECTF_NAMELEN, /* buffer is too small to hold type name */ + ECTF_NOTYPE, /* no type found corresponding to name */ + ECTF_SYNTAX, /* syntax error in type name */ + ECTF_NOTFUNC, /* symtab entry does not refer to a function */ + ECTF_NOFUNCDAT, /* no func info available for function */ + ECTF_NOTDATA, /* symtab entry does not refer to a data obj */ + ECTF_NOTYPEDAT, /* no type info available for object */ + ECTF_NOLABEL, /* no label found corresponding to name */ + ECTF_NOLABELDATA, /* file does not contain any labels */ + ECTF_NOTSUP, /* feature not supported */ + ECTF_NOENUMNAM, /* enum element name not found */ + ECTF_NOMEMBNAM, /* member name not found */ + ECTF_RDONLY, /* CTF container is read-only */ + ECTF_DTFULL, /* CTF type is full (no more members allowed) */ + ECTF_FULL, /* CTF container is full */ + ECTF_DUPMEMBER, /* duplicate member name definition */ + ECTF_CONFLICT /* conflicting type definition present */ +}; + +extern ssize_t ctf_get_ctt_size(const ctf_file_t *, const ctf_type_t *, + ssize_t *, ssize_t *); + +extern const ctf_type_t *ctf_lookup_by_id(ctf_file_t **, ctf_id_t); + +extern int ctf_hash_create(ctf_hash_t *, ulong_t); +extern int ctf_hash_insert(ctf_hash_t *, ctf_file_t *, ushort_t, uint_t); +extern int ctf_hash_define(ctf_hash_t *, ctf_file_t *, ushort_t, uint_t); +extern ctf_helem_t *ctf_hash_lookup(ctf_hash_t *, ctf_file_t *, + const char *, size_t); +extern uint_t ctf_hash_size(const ctf_hash_t *); +extern void ctf_hash_destroy(ctf_hash_t *); + +#define ctf_list_prev(elem) ((void *)(((ctf_list_t *)(elem))->l_prev)) +#define ctf_list_next(elem) ((void *)(((ctf_list_t *)(elem))->l_next)) + +extern void ctf_list_append(ctf_list_t *, void *); +extern void ctf_list_prepend(ctf_list_t *, void *); +extern void ctf_list_delete(ctf_list_t *, void *); + +extern void ctf_dtd_insert(ctf_file_t *, ctf_dtdef_t *); +extern void ctf_dtd_delete(ctf_file_t *, ctf_dtdef_t *); +extern ctf_dtdef_t *ctf_dtd_lookup(ctf_file_t *, ctf_id_t); + +extern void ctf_decl_init(ctf_decl_t *, char *, size_t); +extern void ctf_decl_fini(ctf_decl_t *); +extern void ctf_decl_push(ctf_decl_t *, ctf_file_t *, ctf_id_t); +extern void ctf_decl_sprintf(ctf_decl_t *, const char *, ...); + +extern const char *ctf_strraw(ctf_file_t *, uint_t); +extern const char *ctf_strptr(ctf_file_t *, uint_t); + +extern ctf_file_t *ctf_set_open_errno(int *, int); +extern long ctf_set_errno(ctf_file_t *, int); + +extern const void *ctf_sect_mmap(ctf_sect_t *, int); +extern void ctf_sect_munmap(const ctf_sect_t *); + +extern void *ctf_data_alloc(size_t); +extern void ctf_data_free(void *, size_t); +extern void ctf_data_protect(void *, size_t); + +extern void *ctf_alloc(size_t); +extern void ctf_free(void *, size_t); + +extern char *ctf_strdup(const char *); +extern const char *ctf_strerror(int); +extern void ctf_dprintf(const char *, ...); + +extern void *ctf_zopen(int *); + +extern const char _CTF_SECTION[]; /* name of CTF ELF section */ +extern const char _CTF_NULLSTR[]; /* empty string */ + +extern int _libctf_version; /* library client version */ +extern int _libctf_debug; /* debugging messages enabled */ + +#ifdef __cplusplus +} +#endif + +#endif /* _CTF_IMPL_H */ diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_labels.c b/cddl/contrib/opensolaris/common/ctf/ctf_labels.c new file mode 100644 index 0000000..ddcb1d3 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_labels.c @@ -0,0 +1,153 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2002-2003 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <ctf_impl.h> + +static int +extract_label_info(ctf_file_t *fp, const ctf_lblent_t **ctl, uint_t *num_labels) +{ + const ctf_header_t *h; + + /* + * Labels are only supported in V2 or later + */ + if (fp->ctf_version < CTF_VERSION_2) + return (ctf_set_errno(fp, ECTF_NOTSUP)); + + h = (const ctf_header_t *)fp->ctf_data.cts_data; + + /* LINTED - pointer alignment */ + *ctl = (const ctf_lblent_t *)(fp->ctf_buf + h->cth_lbloff); + *num_labels = (h->cth_objtoff - h->cth_lbloff) / sizeof (ctf_lblent_t); + + return (0); +} + +/* + * Returns the topmost label, or NULL if any errors are encountered + */ +const char * +ctf_label_topmost(ctf_file_t *fp) +{ + const ctf_lblent_t *ctlp; + const char *s; + uint_t num_labels; + + if (extract_label_info(fp, &ctlp, &num_labels) == CTF_ERR) + return (NULL); /* errno is set */ + + if (num_labels == 0) { + (void) ctf_set_errno(fp, ECTF_NOLABELDATA); + return (NULL); + } + + if ((s = ctf_strraw(fp, (ctlp + num_labels - 1)->ctl_label)) == NULL) + (void) ctf_set_errno(fp, ECTF_CORRUPT); + + return (s); +} + +/* + * Iterate over all labels. We pass the label string and the lblinfo_t struct + * to the specified callback function. + */ +int +ctf_label_iter(ctf_file_t *fp, ctf_label_f *func, void *arg) +{ + const ctf_lblent_t *ctlp; + uint_t i, num_labels; + ctf_lblinfo_t linfo; + const char *lname; + int rc; + + if (extract_label_info(fp, &ctlp, &num_labels) == CTF_ERR) + return (CTF_ERR); /* errno is set */ + + if (num_labels == 0) + return (ctf_set_errno(fp, ECTF_NOLABELDATA)); + + for (i = 0; i < num_labels; i++, ctlp++) { + if ((lname = ctf_strraw(fp, ctlp->ctl_label)) == NULL) { + ctf_dprintf("failed to decode label %u with " + "typeidx %u\n", ctlp->ctl_label, ctlp->ctl_typeidx); + return (ctf_set_errno(fp, ECTF_CORRUPT)); + } + + linfo.ctb_typeidx = ctlp->ctl_typeidx; + if ((rc = func(lname, &linfo, arg)) != 0) + return (rc); + } + + return (0); +} + +typedef struct linfo_cb_arg { + const char *lca_name; /* Label we want to retrieve info for */ + ctf_lblinfo_t *lca_info; /* Where to store the info about the label */ +} linfo_cb_arg_t; + +static int +label_info_cb(const char *lname, const ctf_lblinfo_t *linfo, void *arg) +{ + /* + * If lname matches the label we are looking for, copy the + * lblinfo_t struct for the caller. + */ + if (strcmp(lname, ((linfo_cb_arg_t *)arg)->lca_name) == 0) { + /* + * Allow caller not to allocate storage to test if label exists + */ + if (((linfo_cb_arg_t *)arg)->lca_info != NULL) + bcopy(linfo, ((linfo_cb_arg_t *)arg)->lca_info, + sizeof (ctf_lblinfo_t)); + return (1); /* Indicate we found a match */ + } + + return (0); +} + +/* + * Retrieve information about the label with name "lname" + */ +int +ctf_label_info(ctf_file_t *fp, const char *lname, ctf_lblinfo_t *linfo) +{ + linfo_cb_arg_t cb_arg; + int rc; + + cb_arg.lca_name = lname; + cb_arg.lca_info = linfo; + + if ((rc = ctf_label_iter(fp, label_info_cb, &cb_arg)) == CTF_ERR) + return (rc); + + if (rc != 1) + return (ctf_set_errno(fp, ECTF_NOLABEL)); + + return (0); +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_lookup.c b/cddl/contrib/opensolaris/common/ctf/ctf_lookup.c new file mode 100644 index 0000000..f8fa724 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_lookup.c @@ -0,0 +1,313 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2006 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <sys/sysmacros.h> +#include <ctf_impl.h> + +/* + * Compare the given input string and length against a table of known C storage + * qualifier keywords. We just ignore these in ctf_lookup_by_name, below. To + * do this quickly, we use a pre-computed Perfect Hash Function similar to the + * technique originally described in the classic paper: + * + * R.J. Cichelli, "Minimal Perfect Hash Functions Made Simple", + * Communications of the ACM, Volume 23, Issue 1, January 1980, pp. 17-19. + * + * For an input string S of length N, we use hash H = S[N - 1] + N - 105, which + * for the current set of qualifiers yields a unique H in the range [0 .. 20]. + * The hash can be modified when the keyword set changes as necessary. We also + * store the length of each keyword and check it prior to the final strcmp(). + */ +static int +isqualifier(const char *s, size_t len) +{ + static const struct qual { + const char *q_name; + size_t q_len; + } qhash[] = { + { "static", 6 }, { "", 0 }, { "", 0 }, { "", 0 }, + { "volatile", 8 }, { "", 0 }, { "", 0 }, { "", 0 }, { "", 0 }, + { "", 0 }, { "auto", 4 }, { "extern", 6 }, { "", 0 }, { "", 0 }, + { "", 0 }, { "", 0 }, { "const", 5 }, { "register", 8 }, + { "", 0 }, { "restrict", 8 }, { "_Restrict", 9 } + }; + + int h = s[len - 1] + (int)len - 105; + const struct qual *qp = &qhash[h]; + + return (h >= 0 && h < sizeof (qhash) / sizeof (qhash[0]) && + len == qp->q_len && strncmp(qp->q_name, s, qp->q_len) == 0); +} + +/* + * Attempt to convert the given C type name into the corresponding CTF type ID. + * It is not possible to do complete and proper conversion of type names + * without implementing a more full-fledged parser, which is necessary to + * handle things like types that are function pointers to functions that + * have arguments that are function pointers, and fun stuff like that. + * Instead, this function implements a very simple conversion algorithm that + * finds the things that we actually care about: structs, unions, enums, + * integers, floats, typedefs, and pointers to any of these named types. + */ +ctf_id_t +ctf_lookup_by_name(ctf_file_t *fp, const char *name) +{ + static const char delimiters[] = " \t\n\r\v\f*"; + + const ctf_lookup_t *lp; + const ctf_helem_t *hp; + const char *p, *q, *end; + ctf_id_t type = 0; + ctf_id_t ntype, ptype; + + if (name == NULL) + return (ctf_set_errno(fp, EINVAL)); + + for (p = name, end = name + strlen(name); *p != '\0'; p = q) { + while (isspace(*p)) + p++; /* skip leading ws */ + + if (p == end) + break; + + if ((q = strpbrk(p + 1, delimiters)) == NULL) + q = end; /* compare until end */ + + if (*p == '*') { + /* + * Find a pointer to type by looking in fp->ctf_ptrtab. + * If we can't find a pointer to the given type, see if + * we can compute a pointer to the type resulting from + * resolving the type down to its base type and use + * that instead. This helps with cases where the CTF + * data includes "struct foo *" but not "foo_t *" and + * the user tries to access "foo_t *" in the debugger. + */ + ntype = fp->ctf_ptrtab[CTF_TYPE_TO_INDEX(type)]; + if (ntype == 0) { + ntype = ctf_type_resolve(fp, type); + if (ntype == CTF_ERR || (ntype = fp->ctf_ptrtab[ + CTF_TYPE_TO_INDEX(ntype)]) == 0) { + (void) ctf_set_errno(fp, ECTF_NOTYPE); + goto err; + } + } + + type = CTF_INDEX_TO_TYPE(ntype, + (fp->ctf_flags & LCTF_CHILD)); + + q = p + 1; + continue; + } + + if (isqualifier(p, (size_t)(q - p))) + continue; /* skip qualifier keyword */ + + for (lp = fp->ctf_lookups; lp->ctl_prefix != NULL; lp++) { + if (lp->ctl_prefix[0] == '\0' || + strncmp(p, lp->ctl_prefix, (size_t)(q - p)) == 0) { + for (p += lp->ctl_len; isspace(*p); p++) + continue; /* skip prefix and next ws */ + + if ((q = strchr(p, '*')) == NULL) + q = end; /* compare until end */ + + while (isspace(q[-1])) + q--; /* exclude trailing ws */ + + if ((hp = ctf_hash_lookup(lp->ctl_hash, fp, p, + (size_t)(q - p))) == NULL) { + (void) ctf_set_errno(fp, ECTF_NOTYPE); + goto err; + } + + type = hp->h_type; + break; + } + } + + if (lp->ctl_prefix == NULL) { + (void) ctf_set_errno(fp, ECTF_NOTYPE); + goto err; + } + } + + if (*p != '\0' || type == 0) + return (ctf_set_errno(fp, ECTF_SYNTAX)); + + return (type); + +err: + if (fp->ctf_parent != NULL && + (ptype = ctf_lookup_by_name(fp->ctf_parent, name)) != CTF_ERR) + return (ptype); + + return (CTF_ERR); +} + +/* + * Given a symbol table index, return the type of the data object described + * by the corresponding entry in the symbol table. + */ +ctf_id_t +ctf_lookup_by_symbol(ctf_file_t *fp, ulong_t symidx) +{ + const ctf_sect_t *sp = &fp->ctf_symtab; + ctf_id_t type; + + if (sp->cts_data == NULL) + return (ctf_set_errno(fp, ECTF_NOSYMTAB)); + + if (symidx >= fp->ctf_nsyms) + return (ctf_set_errno(fp, EINVAL)); + + if (sp->cts_entsize == sizeof (Elf32_Sym)) { + const Elf32_Sym *symp = (Elf32_Sym *)sp->cts_data + symidx; + if (ELF32_ST_TYPE(symp->st_info) != STT_OBJECT) + return (ctf_set_errno(fp, ECTF_NOTDATA)); + } else { + const Elf64_Sym *symp = (Elf64_Sym *)sp->cts_data + symidx; + if (ELF64_ST_TYPE(symp->st_info) != STT_OBJECT) + return (ctf_set_errno(fp, ECTF_NOTDATA)); + } + + if (fp->ctf_sxlate[symidx] == -1u) + return (ctf_set_errno(fp, ECTF_NOTYPEDAT)); + + type = *(ushort_t *)((uintptr_t)fp->ctf_buf + fp->ctf_sxlate[symidx]); + if (type == 0) + return (ctf_set_errno(fp, ECTF_NOTYPEDAT)); + + return (type); +} + +/* + * Return the pointer to the internal CTF type data corresponding to the + * given type ID. If the ID is invalid, the function returns NULL. + * This function is not exported outside of the library. + */ +const ctf_type_t * +ctf_lookup_by_id(ctf_file_t **fpp, ctf_id_t type) +{ + ctf_file_t *fp = *fpp; /* caller passes in starting CTF container */ + + if ((fp->ctf_flags & LCTF_CHILD) && CTF_TYPE_ISPARENT(type) && + (fp = fp->ctf_parent) == NULL) { + (void) ctf_set_errno(*fpp, ECTF_NOPARENT); + return (NULL); + } + + type = CTF_TYPE_TO_INDEX(type); + if (type > 0 && type <= fp->ctf_typemax) { + *fpp = fp; /* function returns ending CTF container */ + return (LCTF_INDEX_TO_TYPEPTR(fp, type)); + } + + (void) ctf_set_errno(fp, ECTF_BADID); + return (NULL); +} + +/* + * Given a symbol table index, return the info for the function described + * by the corresponding entry in the symbol table. + */ +int +ctf_func_info(ctf_file_t *fp, ulong_t symidx, ctf_funcinfo_t *fip) +{ + const ctf_sect_t *sp = &fp->ctf_symtab; + const ushort_t *dp; + ushort_t info, kind, n; + + if (sp->cts_data == NULL) + return (ctf_set_errno(fp, ECTF_NOSYMTAB)); + + if (symidx >= fp->ctf_nsyms) + return (ctf_set_errno(fp, EINVAL)); + + if (sp->cts_entsize == sizeof (Elf32_Sym)) { + const Elf32_Sym *symp = (Elf32_Sym *)sp->cts_data + symidx; + if (ELF32_ST_TYPE(symp->st_info) != STT_FUNC) + return (ctf_set_errno(fp, ECTF_NOTFUNC)); + } else { + const Elf64_Sym *symp = (Elf64_Sym *)sp->cts_data + symidx; + if (ELF64_ST_TYPE(symp->st_info) != STT_FUNC) + return (ctf_set_errno(fp, ECTF_NOTFUNC)); + } + + if (fp->ctf_sxlate[symidx] == -1u) + return (ctf_set_errno(fp, ECTF_NOFUNCDAT)); + + dp = (ushort_t *)((uintptr_t)fp->ctf_buf + fp->ctf_sxlate[symidx]); + + info = *dp++; + kind = LCTF_INFO_KIND(fp, info); + n = LCTF_INFO_VLEN(fp, info); + + if (kind == CTF_K_UNKNOWN && n == 0) + return (ctf_set_errno(fp, ECTF_NOFUNCDAT)); + + if (kind != CTF_K_FUNCTION) + return (ctf_set_errno(fp, ECTF_CORRUPT)); + + fip->ctc_return = *dp++; + fip->ctc_argc = n; + fip->ctc_flags = 0; + + if (n != 0 && dp[n - 1] == 0) { + fip->ctc_flags |= CTF_FUNC_VARARG; + fip->ctc_argc--; + } + + return (0); +} + +/* + * Given a symbol table index, return the arguments for the function described + * by the corresponding entry in the symbol table. + */ +int +ctf_func_args(ctf_file_t *fp, ulong_t symidx, uint_t argc, ctf_id_t *argv) +{ + const ushort_t *dp; + ctf_funcinfo_t f; + + if (ctf_func_info(fp, symidx, &f) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + /* + * The argument data is two ushort_t's past the translation table + * offset: one for the function info, and one for the return type. + */ + dp = (ushort_t *)((uintptr_t)fp->ctf_buf + fp->ctf_sxlate[symidx]) + 2; + + for (argc = MIN(argc, f.ctc_argc); argc != 0; argc--) + *argv++ = *dp++; + + return (0); +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_open.c b/cddl/contrib/opensolaris/common/ctf/ctf_open.c new file mode 100644 index 0000000..e49a4cb --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_open.c @@ -0,0 +1,954 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2006 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <ctf_impl.h> +#include <sys/mman.h> +#include <sys/zmod.h> + +static const ctf_dmodel_t _libctf_models[] = { + { "ILP32", CTF_MODEL_ILP32, 4, 1, 2, 4, 4 }, + { "LP64", CTF_MODEL_LP64, 8, 1, 2, 4, 8 }, + { NULL, 0, 0, 0, 0, 0, 0 } +}; + +const char _CTF_SECTION[] = ".SUNW_ctf"; +const char _CTF_NULLSTR[] = ""; + +int _libctf_version = CTF_VERSION; /* library client version */ +int _libctf_debug = 0; /* debugging messages enabled */ + +static ushort_t +get_kind_v1(ushort_t info) +{ + return (CTF_INFO_KIND_V1(info)); +} + +static ushort_t +get_kind_v2(ushort_t info) +{ + return (CTF_INFO_KIND(info)); +} + +static ushort_t +get_root_v1(ushort_t info) +{ + return (CTF_INFO_ISROOT_V1(info)); +} + +static ushort_t +get_root_v2(ushort_t info) +{ + return (CTF_INFO_ISROOT(info)); +} + +static ushort_t +get_vlen_v1(ushort_t info) +{ + return (CTF_INFO_VLEN_V1(info)); +} + +static ushort_t +get_vlen_v2(ushort_t info) +{ + return (CTF_INFO_VLEN(info)); +} + +static const ctf_fileops_t ctf_fileops[] = { + { NULL, NULL }, + { get_kind_v1, get_root_v1, get_vlen_v1 }, + { get_kind_v2, get_root_v2, get_vlen_v2 }, +}; + +/* + * Convert a 32-bit ELF symbol into GElf (Elf64) and return a pointer to it. + */ +static Elf64_Sym * +sym_to_gelf(const Elf32_Sym *src, Elf64_Sym *dst) +{ + dst->st_name = src->st_name; + dst->st_value = src->st_value; + dst->st_size = src->st_size; + dst->st_info = src->st_info; + dst->st_other = src->st_other; + dst->st_shndx = src->st_shndx; + + return (dst); +} + +/* + * Initialize the symtab translation table by filling each entry with the + * offset of the CTF type or function data corresponding to each STT_FUNC or + * STT_OBJECT entry in the symbol table. + */ +static int +init_symtab(ctf_file_t *fp, const ctf_header_t *hp, + const ctf_sect_t *sp, const ctf_sect_t *strp) +{ + const uchar_t *symp = sp->cts_data; + uint_t *xp = fp->ctf_sxlate; + uint_t *xend = xp + fp->ctf_nsyms; + + uint_t objtoff = hp->cth_objtoff; + uint_t funcoff = hp->cth_funcoff; + + ushort_t info, vlen; + Elf64_Sym sym, *gsp; + const char *name; + + /* + * The CTF data object and function type sections are ordered to match + * the relative order of the respective symbol types in the symtab. + * If no type information is available for a symbol table entry, a + * pad is inserted in the CTF section. As a further optimization, + * anonymous or undefined symbols are omitted from the CTF data. + */ + for (; xp < xend; xp++, symp += sp->cts_entsize) { + if (sp->cts_entsize == sizeof (Elf32_Sym)) + gsp = sym_to_gelf((Elf32_Sym *)(uintptr_t)symp, &sym); + else + gsp = (Elf64_Sym *)(uintptr_t)symp; + + if (gsp->st_name < strp->cts_size) + name = (const char *)strp->cts_data + gsp->st_name; + else + name = _CTF_NULLSTR; + + if (gsp->st_name == 0 || gsp->st_shndx == SHN_UNDEF || + strcmp(name, "_START_") == 0 || + strcmp(name, "_END_") == 0) { + *xp = -1u; + continue; + } + + switch (ELF64_ST_TYPE(gsp->st_info)) { + case STT_OBJECT: + if (objtoff >= hp->cth_funcoff || + (gsp->st_shndx == SHN_ABS && gsp->st_value == 0)) { + *xp = -1u; + break; + } + + *xp = objtoff; + objtoff += sizeof (ushort_t); + break; + + case STT_FUNC: + if (funcoff >= hp->cth_typeoff) { + *xp = -1u; + break; + } + + *xp = funcoff; + + info = *(ushort_t *)((uintptr_t)fp->ctf_buf + funcoff); + vlen = LCTF_INFO_VLEN(fp, info); + + /* + * If we encounter a zero pad at the end, just skip it. + * Otherwise skip over the function and its return type + * (+2) and the argument list (vlen). + */ + if (LCTF_INFO_KIND(fp, info) == CTF_K_UNKNOWN && + vlen == 0) + funcoff += sizeof (ushort_t); /* skip pad */ + else + funcoff += sizeof (ushort_t) * (vlen + 2); + break; + + default: + *xp = -1u; + break; + } + } + + ctf_dprintf("loaded %lu symtab entries\n", fp->ctf_nsyms); + return (0); +} + +/* + * Initialize the type ID translation table with the byte offset of each type, + * and initialize the hash tables of each named type. + */ +static int +init_types(ctf_file_t *fp, const ctf_header_t *cth) +{ + /* LINTED - pointer alignment */ + const ctf_type_t *tbuf = (ctf_type_t *)(fp->ctf_buf + cth->cth_typeoff); + /* LINTED - pointer alignment */ + const ctf_type_t *tend = (ctf_type_t *)(fp->ctf_buf + cth->cth_stroff); + + ulong_t pop[CTF_K_MAX + 1] = { 0 }; + const ctf_type_t *tp; + ctf_hash_t *hp; + ushort_t id, dst; + uint_t *xp; + + /* + * We initially determine whether the container is a child or a parent + * based on the value of cth_parname. To support containers that pre- + * date cth_parname, we also scan the types themselves for references + * to values in the range reserved for child types in our first pass. + */ + int child = cth->cth_parname != 0; + int nlstructs = 0, nlunions = 0; + int err; + + /* + * We make two passes through the entire type section. In this first + * pass, we count the number of each type and the total number of types. + */ + for (tp = tbuf; tp < tend; fp->ctf_typemax++) { + ushort_t kind = LCTF_INFO_KIND(fp, tp->ctt_info); + ulong_t vlen = LCTF_INFO_VLEN(fp, tp->ctt_info); + ssize_t size, increment; + + size_t vbytes; + uint_t n; + + (void) ctf_get_ctt_size(fp, tp, &size, &increment); + + switch (kind) { + case CTF_K_INTEGER: + case CTF_K_FLOAT: + vbytes = sizeof (uint_t); + break; + case CTF_K_ARRAY: + vbytes = sizeof (ctf_array_t); + break; + case CTF_K_FUNCTION: + vbytes = sizeof (ushort_t) * (vlen + (vlen & 1)); + break; + case CTF_K_STRUCT: + case CTF_K_UNION: + if (fp->ctf_version == CTF_VERSION_1 || + size < CTF_LSTRUCT_THRESH) { + ctf_member_t *mp = (ctf_member_t *) + ((uintptr_t)tp + increment); + + vbytes = sizeof (ctf_member_t) * vlen; + for (n = vlen; n != 0; n--, mp++) + child |= CTF_TYPE_ISCHILD(mp->ctm_type); + } else { + ctf_lmember_t *lmp = (ctf_lmember_t *) + ((uintptr_t)tp + increment); + + vbytes = sizeof (ctf_lmember_t) * vlen; + for (n = vlen; n != 0; n--, lmp++) + child |= + CTF_TYPE_ISCHILD(lmp->ctlm_type); + } + break; + case CTF_K_ENUM: + vbytes = sizeof (ctf_enum_t) * vlen; + break; + case CTF_K_FORWARD: + /* + * For forward declarations, ctt_type is the CTF_K_* + * kind for the tag, so bump that population count too. + * If ctt_type is unknown, treat the tag as a struct. + */ + if (tp->ctt_type == CTF_K_UNKNOWN || + tp->ctt_type >= CTF_K_MAX) + pop[CTF_K_STRUCT]++; + else + pop[tp->ctt_type]++; + /*FALLTHRU*/ + case CTF_K_UNKNOWN: + vbytes = 0; + break; + case CTF_K_POINTER: + case CTF_K_TYPEDEF: + case CTF_K_VOLATILE: + case CTF_K_CONST: + case CTF_K_RESTRICT: + child |= CTF_TYPE_ISCHILD(tp->ctt_type); + vbytes = 0; + break; + default: + ctf_dprintf("detected invalid CTF kind -- %u\n", kind); + return (ECTF_CORRUPT); + } + tp = (ctf_type_t *)((uintptr_t)tp + increment + vbytes); + pop[kind]++; + } + + /* + * If we detected a reference to a child type ID, then we know this + * container is a child and may have a parent's types imported later. + */ + if (child) { + ctf_dprintf("CTF container %p is a child\n", (void *)fp); + fp->ctf_flags |= LCTF_CHILD; + } else + ctf_dprintf("CTF container %p is a parent\n", (void *)fp); + + /* + * Now that we've counted up the number of each type, we can allocate + * the hash tables, type translation table, and pointer table. + */ + if ((err = ctf_hash_create(&fp->ctf_structs, pop[CTF_K_STRUCT])) != 0) + return (err); + + if ((err = ctf_hash_create(&fp->ctf_unions, pop[CTF_K_UNION])) != 0) + return (err); + + if ((err = ctf_hash_create(&fp->ctf_enums, pop[CTF_K_ENUM])) != 0) + return (err); + + if ((err = ctf_hash_create(&fp->ctf_names, + pop[CTF_K_INTEGER] + pop[CTF_K_FLOAT] + pop[CTF_K_FUNCTION] + + pop[CTF_K_TYPEDEF] + pop[CTF_K_POINTER] + pop[CTF_K_VOLATILE] + + pop[CTF_K_CONST] + pop[CTF_K_RESTRICT])) != 0) + return (err); + + fp->ctf_txlate = ctf_alloc(sizeof (uint_t) * (fp->ctf_typemax + 1)); + fp->ctf_ptrtab = ctf_alloc(sizeof (ushort_t) * (fp->ctf_typemax + 1)); + + if (fp->ctf_txlate == NULL || fp->ctf_ptrtab == NULL) + return (EAGAIN); /* memory allocation failed */ + + xp = fp->ctf_txlate; + *xp++ = 0; /* type id 0 is used as a sentinel value */ + + bzero(fp->ctf_txlate, sizeof (uint_t) * (fp->ctf_typemax + 1)); + bzero(fp->ctf_ptrtab, sizeof (ushort_t) * (fp->ctf_typemax + 1)); + + /* + * In the second pass through the types, we fill in each entry of the + * type and pointer tables and add names to the appropriate hashes. + */ + for (id = 1, tp = tbuf; tp < tend; xp++, id++) { + ushort_t kind = LCTF_INFO_KIND(fp, tp->ctt_info); + ulong_t vlen = LCTF_INFO_VLEN(fp, tp->ctt_info); + ssize_t size, increment; + + const char *name; + size_t vbytes; + ctf_helem_t *hep; + ctf_encoding_t cte; + + (void) ctf_get_ctt_size(fp, tp, &size, &increment); + name = ctf_strptr(fp, tp->ctt_name); + + switch (kind) { + case CTF_K_INTEGER: + case CTF_K_FLOAT: + /* + * Only insert a new integer base type definition if + * this type name has not been defined yet. We re-use + * the names with different encodings for bit-fields. + */ + if ((hep = ctf_hash_lookup(&fp->ctf_names, fp, + name, strlen(name))) == NULL) { + err = ctf_hash_insert(&fp->ctf_names, fp, + CTF_INDEX_TO_TYPE(id, child), tp->ctt_name); + if (err != 0 && err != ECTF_STRTAB) + return (err); + } else if (ctf_type_encoding(fp, hep->h_type, + &cte) == 0 && cte.cte_bits == 0) { + /* + * Work-around SOS8 stabs bug: replace existing + * intrinsic w/ same name if it was zero bits. + */ + hep->h_type = CTF_INDEX_TO_TYPE(id, child); + } + vbytes = sizeof (uint_t); + break; + + case CTF_K_ARRAY: + vbytes = sizeof (ctf_array_t); + break; + + case CTF_K_FUNCTION: + err = ctf_hash_insert(&fp->ctf_names, fp, + CTF_INDEX_TO_TYPE(id, child), tp->ctt_name); + if (err != 0 && err != ECTF_STRTAB) + return (err); + vbytes = sizeof (ushort_t) * (vlen + (vlen & 1)); + break; + + case CTF_K_STRUCT: + err = ctf_hash_define(&fp->ctf_structs, fp, + CTF_INDEX_TO_TYPE(id, child), tp->ctt_name); + + if (err != 0 && err != ECTF_STRTAB) + return (err); + + if (fp->ctf_version == CTF_VERSION_1 || + size < CTF_LSTRUCT_THRESH) + vbytes = sizeof (ctf_member_t) * vlen; + else { + vbytes = sizeof (ctf_lmember_t) * vlen; + nlstructs++; + } + break; + + case CTF_K_UNION: + err = ctf_hash_define(&fp->ctf_unions, fp, + CTF_INDEX_TO_TYPE(id, child), tp->ctt_name); + + if (err != 0 && err != ECTF_STRTAB) + return (err); + + if (fp->ctf_version == CTF_VERSION_1 || + size < CTF_LSTRUCT_THRESH) + vbytes = sizeof (ctf_member_t) * vlen; + else { + vbytes = sizeof (ctf_lmember_t) * vlen; + nlunions++; + } + break; + + case CTF_K_ENUM: + err = ctf_hash_define(&fp->ctf_enums, fp, + CTF_INDEX_TO_TYPE(id, child), tp->ctt_name); + + if (err != 0 && err != ECTF_STRTAB) + return (err); + + vbytes = sizeof (ctf_enum_t) * vlen; + break; + + case CTF_K_TYPEDEF: + err = ctf_hash_insert(&fp->ctf_names, fp, + CTF_INDEX_TO_TYPE(id, child), tp->ctt_name); + if (err != 0 && err != ECTF_STRTAB) + return (err); + vbytes = 0; + break; + + case CTF_K_FORWARD: + /* + * Only insert forward tags into the given hash if the + * type or tag name is not already present. + */ + switch (tp->ctt_type) { + case CTF_K_STRUCT: + hp = &fp->ctf_structs; + break; + case CTF_K_UNION: + hp = &fp->ctf_unions; + break; + case CTF_K_ENUM: + hp = &fp->ctf_enums; + break; + default: + hp = &fp->ctf_structs; + } + + if (ctf_hash_lookup(hp, fp, + name, strlen(name)) == NULL) { + err = ctf_hash_insert(hp, fp, + CTF_INDEX_TO_TYPE(id, child), tp->ctt_name); + if (err != 0 && err != ECTF_STRTAB) + return (err); + } + vbytes = 0; + break; + + case CTF_K_POINTER: + /* + * If the type referenced by the pointer is in this CTF + * container, then store the index of the pointer type + * in fp->ctf_ptrtab[ index of referenced type ]. + */ + if (CTF_TYPE_ISCHILD(tp->ctt_type) == child && + CTF_TYPE_TO_INDEX(tp->ctt_type) <= fp->ctf_typemax) + fp->ctf_ptrtab[ + CTF_TYPE_TO_INDEX(tp->ctt_type)] = id; + /*FALLTHRU*/ + + case CTF_K_VOLATILE: + case CTF_K_CONST: + case CTF_K_RESTRICT: + err = ctf_hash_insert(&fp->ctf_names, fp, + CTF_INDEX_TO_TYPE(id, child), tp->ctt_name); + if (err != 0 && err != ECTF_STRTAB) + return (err); + /*FALLTHRU*/ + + default: + vbytes = 0; + break; + } + + *xp = (uint_t)((uintptr_t)tp - (uintptr_t)fp->ctf_buf); + tp = (ctf_type_t *)((uintptr_t)tp + increment + vbytes); + } + + ctf_dprintf("%lu total types processed\n", fp->ctf_typemax); + ctf_dprintf("%u enum names hashed\n", ctf_hash_size(&fp->ctf_enums)); + ctf_dprintf("%u struct names hashed (%d long)\n", + ctf_hash_size(&fp->ctf_structs), nlstructs); + ctf_dprintf("%u union names hashed (%d long)\n", + ctf_hash_size(&fp->ctf_unions), nlunions); + ctf_dprintf("%u base type names hashed\n", + ctf_hash_size(&fp->ctf_names)); + + /* + * Make an additional pass through the pointer table to find pointers + * that point to anonymous typedef nodes. If we find one, modify the + * pointer table so that the pointer is also known to point to the + * node that is referenced by the anonymous typedef node. + */ + for (id = 1; id <= fp->ctf_typemax; id++) { + if ((dst = fp->ctf_ptrtab[id]) != 0) { + tp = LCTF_INDEX_TO_TYPEPTR(fp, id); + + if (LCTF_INFO_KIND(fp, tp->ctt_info) == CTF_K_TYPEDEF && + strcmp(ctf_strptr(fp, tp->ctt_name), "") == 0 && + CTF_TYPE_ISCHILD(tp->ctt_type) == child && + CTF_TYPE_TO_INDEX(tp->ctt_type) <= fp->ctf_typemax) + fp->ctf_ptrtab[ + CTF_TYPE_TO_INDEX(tp->ctt_type)] = dst; + } + } + + return (0); +} + +/* + * Decode the specified CTF buffer and optional symbol table and create a new + * CTF container representing the symbolic debugging information. This code + * can be used directly by the debugger, or it can be used as the engine for + * ctf_fdopen() or ctf_open(), below. + */ +ctf_file_t * +ctf_bufopen(const ctf_sect_t *ctfsect, const ctf_sect_t *symsect, + const ctf_sect_t *strsect, int *errp) +{ + const ctf_preamble_t *pp; + ctf_header_t hp; + ctf_file_t *fp; + void *buf, *base; + size_t size, hdrsz; + int err; + + if (ctfsect == NULL || ((symsect == NULL) != (strsect == NULL))) + return (ctf_set_open_errno(errp, EINVAL)); + + if (symsect != NULL && symsect->cts_entsize != sizeof (Elf32_Sym) && + symsect->cts_entsize != sizeof (Elf64_Sym)) + return (ctf_set_open_errno(errp, ECTF_SYMTAB)); + + if (symsect != NULL && symsect->cts_data == NULL) + return (ctf_set_open_errno(errp, ECTF_SYMBAD)); + + if (strsect != NULL && strsect->cts_data == NULL) + return (ctf_set_open_errno(errp, ECTF_STRBAD)); + + if (ctfsect->cts_size < sizeof (ctf_preamble_t)) + return (ctf_set_open_errno(errp, ECTF_NOCTFBUF)); + + pp = (const ctf_preamble_t *)ctfsect->cts_data; + + ctf_dprintf("ctf_bufopen: magic=0x%x version=%u\n", + pp->ctp_magic, pp->ctp_version); + + /* + * Validate each part of the CTF header (either V1 or V2). + * First, we validate the preamble (common to all versions). At that + * point, we know specific header version, and can validate the + * version-specific parts including section offsets and alignments. + */ + if (pp->ctp_magic != CTF_MAGIC) + return (ctf_set_open_errno(errp, ECTF_NOCTFBUF)); + + if (pp->ctp_version == CTF_VERSION_2) { + if (ctfsect->cts_size < sizeof (ctf_header_t)) + return (ctf_set_open_errno(errp, ECTF_NOCTFBUF)); + + bcopy(ctfsect->cts_data, &hp, sizeof (hp)); + hdrsz = sizeof (ctf_header_t); + + } else if (pp->ctp_version == CTF_VERSION_1) { + const ctf_header_v1_t *h1p = + (const ctf_header_v1_t *)ctfsect->cts_data; + + if (ctfsect->cts_size < sizeof (ctf_header_v1_t)) + return (ctf_set_open_errno(errp, ECTF_NOCTFBUF)); + + bzero(&hp, sizeof (hp)); + hp.cth_preamble = h1p->cth_preamble; + hp.cth_objtoff = h1p->cth_objtoff; + hp.cth_funcoff = h1p->cth_funcoff; + hp.cth_typeoff = h1p->cth_typeoff; + hp.cth_stroff = h1p->cth_stroff; + hp.cth_strlen = h1p->cth_strlen; + + hdrsz = sizeof (ctf_header_v1_t); + } else + return (ctf_set_open_errno(errp, ECTF_CTFVERS)); + + size = hp.cth_stroff + hp.cth_strlen; + + ctf_dprintf("ctf_bufopen: uncompressed size=%lu\n", (ulong_t)size); + + if (hp.cth_lbloff > size || hp.cth_objtoff > size || + hp.cth_funcoff > size || hp.cth_typeoff > size || + hp.cth_stroff > size) + return (ctf_set_open_errno(errp, ECTF_CORRUPT)); + + if (hp.cth_lbloff > hp.cth_objtoff || + hp.cth_objtoff > hp.cth_funcoff || + hp.cth_funcoff > hp.cth_typeoff || + hp.cth_typeoff > hp.cth_stroff) + return (ctf_set_open_errno(errp, ECTF_CORRUPT)); + + if ((hp.cth_lbloff & 3) || (hp.cth_objtoff & 1) || + (hp.cth_funcoff & 1) || (hp.cth_typeoff & 3)) + return (ctf_set_open_errno(errp, ECTF_CORRUPT)); + + /* + * Once everything is determined to be valid, attempt to decompress + * the CTF data buffer if it is compressed. Otherwise we just put + * the data section's buffer pointer into ctf_buf, below. + */ + if (hp.cth_flags & CTF_F_COMPRESS) { + size_t srclen, dstlen; + const void *src; + int rc = Z_OK; + + if (ctf_zopen(errp) == NULL) + return (NULL); /* errp is set for us */ + + if ((base = ctf_data_alloc(size + hdrsz)) == MAP_FAILED) + return (ctf_set_open_errno(errp, ECTF_ZALLOC)); + + bcopy(ctfsect->cts_data, base, hdrsz); + ((ctf_preamble_t *)base)->ctp_flags &= ~CTF_F_COMPRESS; + buf = (uchar_t *)base + hdrsz; + + src = (uchar_t *)ctfsect->cts_data + hdrsz; + srclen = ctfsect->cts_size - hdrsz; + dstlen = size; + + if ((rc = z_uncompress(buf, &dstlen, src, srclen)) != Z_OK) { + ctf_dprintf("zlib inflate err: %s\n", z_strerror(rc)); + ctf_data_free(base, size + hdrsz); + return (ctf_set_open_errno(errp, ECTF_DECOMPRESS)); + } + + if (dstlen != size) { + ctf_dprintf("zlib inflate short -- got %lu of %lu " + "bytes\n", (ulong_t)dstlen, (ulong_t)size); + ctf_data_free(base, size + hdrsz); + return (ctf_set_open_errno(errp, ECTF_CORRUPT)); + } + + ctf_data_protect(base, size + hdrsz); + + } else { + base = (void *)ctfsect->cts_data; + buf = (uchar_t *)base + hdrsz; + } + + /* + * Once we have uncompressed and validated the CTF data buffer, we can + * proceed with allocating a ctf_file_t and initializing it. + */ + if ((fp = ctf_alloc(sizeof (ctf_file_t))) == NULL) + return (ctf_set_open_errno(errp, EAGAIN)); + + bzero(fp, sizeof (ctf_file_t)); + fp->ctf_version = hp.cth_version; + fp->ctf_fileops = &ctf_fileops[hp.cth_version]; + bcopy(ctfsect, &fp->ctf_data, sizeof (ctf_sect_t)); + + if (symsect != NULL) { + bcopy(symsect, &fp->ctf_symtab, sizeof (ctf_sect_t)); + bcopy(strsect, &fp->ctf_strtab, sizeof (ctf_sect_t)); + } + + if (fp->ctf_data.cts_name != NULL) + fp->ctf_data.cts_name = ctf_strdup(fp->ctf_data.cts_name); + if (fp->ctf_symtab.cts_name != NULL) + fp->ctf_symtab.cts_name = ctf_strdup(fp->ctf_symtab.cts_name); + if (fp->ctf_strtab.cts_name != NULL) + fp->ctf_strtab.cts_name = ctf_strdup(fp->ctf_strtab.cts_name); + + if (fp->ctf_data.cts_name == NULL) + fp->ctf_data.cts_name = _CTF_NULLSTR; + if (fp->ctf_symtab.cts_name == NULL) + fp->ctf_symtab.cts_name = _CTF_NULLSTR; + if (fp->ctf_strtab.cts_name == NULL) + fp->ctf_strtab.cts_name = _CTF_NULLSTR; + + fp->ctf_str[CTF_STRTAB_0].cts_strs = (const char *)buf + hp.cth_stroff; + fp->ctf_str[CTF_STRTAB_0].cts_len = hp.cth_strlen; + + if (strsect != NULL) { + fp->ctf_str[CTF_STRTAB_1].cts_strs = strsect->cts_data; + fp->ctf_str[CTF_STRTAB_1].cts_len = strsect->cts_size; + } + + fp->ctf_base = base; + fp->ctf_buf = buf; + fp->ctf_size = size + hdrsz; + + /* + * If we have a parent container name and label, store the relocated + * string pointers in the CTF container for easy access later. + */ + if (hp.cth_parlabel != 0) + fp->ctf_parlabel = ctf_strptr(fp, hp.cth_parlabel); + if (hp.cth_parname != 0) + fp->ctf_parname = ctf_strptr(fp, hp.cth_parname); + + ctf_dprintf("ctf_bufopen: parent name %s (label %s)\n", + fp->ctf_parname ? fp->ctf_parname : "<NULL>", + fp->ctf_parlabel ? fp->ctf_parlabel : "<NULL>"); + + /* + * If we have a symbol table section, allocate and initialize + * the symtab translation table, pointed to by ctf_sxlate. + */ + if (symsect != NULL) { + fp->ctf_nsyms = symsect->cts_size / symsect->cts_entsize; + fp->ctf_sxlate = ctf_alloc(fp->ctf_nsyms * sizeof (uint_t)); + + if (fp->ctf_sxlate == NULL) { + (void) ctf_set_open_errno(errp, EAGAIN); + goto bad; + } + + if ((err = init_symtab(fp, &hp, symsect, strsect)) != 0) { + (void) ctf_set_open_errno(errp, err); + goto bad; + } + } + + if ((err = init_types(fp, &hp)) != 0) { + (void) ctf_set_open_errno(errp, err); + goto bad; + } + + /* + * Initialize the ctf_lookup_by_name top-level dictionary. We keep an + * array of type name prefixes and the corresponding ctf_hash to use. + * NOTE: This code must be kept in sync with the code in ctf_update(). + */ + fp->ctf_lookups[0].ctl_prefix = "struct"; + fp->ctf_lookups[0].ctl_len = strlen(fp->ctf_lookups[0].ctl_prefix); + fp->ctf_lookups[0].ctl_hash = &fp->ctf_structs; + fp->ctf_lookups[1].ctl_prefix = "union"; + fp->ctf_lookups[1].ctl_len = strlen(fp->ctf_lookups[1].ctl_prefix); + fp->ctf_lookups[1].ctl_hash = &fp->ctf_unions; + fp->ctf_lookups[2].ctl_prefix = "enum"; + fp->ctf_lookups[2].ctl_len = strlen(fp->ctf_lookups[2].ctl_prefix); + fp->ctf_lookups[2].ctl_hash = &fp->ctf_enums; + fp->ctf_lookups[3].ctl_prefix = _CTF_NULLSTR; + fp->ctf_lookups[3].ctl_len = strlen(fp->ctf_lookups[3].ctl_prefix); + fp->ctf_lookups[3].ctl_hash = &fp->ctf_names; + fp->ctf_lookups[4].ctl_prefix = NULL; + fp->ctf_lookups[4].ctl_len = 0; + fp->ctf_lookups[4].ctl_hash = NULL; + + if (symsect != NULL) { + if (symsect->cts_entsize == sizeof (Elf64_Sym)) + (void) ctf_setmodel(fp, CTF_MODEL_LP64); + else + (void) ctf_setmodel(fp, CTF_MODEL_ILP32); + } else + (void) ctf_setmodel(fp, CTF_MODEL_NATIVE); + + fp->ctf_refcnt = 1; + return (fp); + +bad: + ctf_close(fp); + return (NULL); +} + +/* + * Close the specified CTF container and free associated data structures. Note + * that ctf_close() is a reference counted operation: if the specified file is + * the parent of other active containers, its reference count will be greater + * than one and it will be freed later when no active children exist. + */ +void +ctf_close(ctf_file_t *fp) +{ + ctf_dtdef_t *dtd, *ntd; + + if (fp == NULL) + return; /* allow ctf_close(NULL) to simplify caller code */ + + ctf_dprintf("ctf_close(%p) refcnt=%u\n", (void *)fp, fp->ctf_refcnt); + + if (fp->ctf_refcnt > 1) { + fp->ctf_refcnt--; + return; + } + + if (fp->ctf_parent != NULL) + ctf_close(fp->ctf_parent); + + for (dtd = ctf_list_next(&fp->ctf_dtdefs); dtd != NULL; dtd = ntd) { + ntd = ctf_list_next(dtd); + ctf_dtd_delete(fp, dtd); + } + + ctf_free(fp->ctf_dthash, fp->ctf_dthashlen * sizeof (ctf_dtdef_t *)); + + if (fp->ctf_flags & LCTF_MMAP) { + if (fp->ctf_data.cts_data != NULL) + ctf_sect_munmap(&fp->ctf_data); + if (fp->ctf_symtab.cts_data != NULL) + ctf_sect_munmap(&fp->ctf_symtab); + if (fp->ctf_strtab.cts_data != NULL) + ctf_sect_munmap(&fp->ctf_strtab); + } + + if (fp->ctf_data.cts_name != _CTF_NULLSTR && + fp->ctf_data.cts_name != NULL) { + ctf_free((char *)fp->ctf_data.cts_name, + strlen(fp->ctf_data.cts_name) + 1); + } + + if (fp->ctf_symtab.cts_name != _CTF_NULLSTR && + fp->ctf_symtab.cts_name != NULL) { + ctf_free((char *)fp->ctf_symtab.cts_name, + strlen(fp->ctf_symtab.cts_name) + 1); + } + + if (fp->ctf_strtab.cts_name != _CTF_NULLSTR && + fp->ctf_strtab.cts_name != NULL) { + ctf_free((char *)fp->ctf_strtab.cts_name, + strlen(fp->ctf_strtab.cts_name) + 1); + } + + if (fp->ctf_base != fp->ctf_data.cts_data && fp->ctf_base != NULL) + ctf_data_free((void *)fp->ctf_base, fp->ctf_size); + + if (fp->ctf_sxlate != NULL) + ctf_free(fp->ctf_sxlate, sizeof (uint_t) * fp->ctf_nsyms); + + if (fp->ctf_txlate != NULL) { + ctf_free(fp->ctf_txlate, + sizeof (uint_t) * (fp->ctf_typemax + 1)); + } + + if (fp->ctf_ptrtab != NULL) { + ctf_free(fp->ctf_ptrtab, + sizeof (ushort_t) * (fp->ctf_typemax + 1)); + } + + ctf_hash_destroy(&fp->ctf_structs); + ctf_hash_destroy(&fp->ctf_unions); + ctf_hash_destroy(&fp->ctf_enums); + ctf_hash_destroy(&fp->ctf_names); + + ctf_free(fp, sizeof (ctf_file_t)); +} + +/* + * Return the CTF handle for the parent CTF container, if one exists. + * Otherwise return NULL to indicate this container has no imported parent. + */ +ctf_file_t * +ctf_parent_file(ctf_file_t *fp) +{ + return (fp->ctf_parent); +} + +/* + * Return the name of the parent CTF container, if one exists. Otherwise + * return NULL to indicate this container is a root container. + */ +const char * +ctf_parent_name(ctf_file_t *fp) +{ + return (fp->ctf_parname); +} + +/* + * Import the types from the specified parent container by storing a pointer + * to it in ctf_parent and incrementing its reference count. Only one parent + * is allowed: if a parent already exists, it is replaced by the new parent. + */ +int +ctf_import(ctf_file_t *fp, ctf_file_t *pfp) +{ + if (fp == NULL || fp == pfp || (pfp != NULL && pfp->ctf_refcnt == 0)) + return (ctf_set_errno(fp, EINVAL)); + + if (pfp != NULL && pfp->ctf_dmodel != fp->ctf_dmodel) + return (ctf_set_errno(fp, ECTF_DMODEL)); + + if (fp->ctf_parent != NULL) + ctf_close(fp->ctf_parent); + + if (pfp != NULL) { + fp->ctf_flags |= LCTF_CHILD; + pfp->ctf_refcnt++; + } + + fp->ctf_parent = pfp; + return (0); +} + +/* + * Set the data model constant for the CTF container. + */ +int +ctf_setmodel(ctf_file_t *fp, int model) +{ + const ctf_dmodel_t *dp; + + for (dp = _libctf_models; dp->ctd_name != NULL; dp++) { + if (dp->ctd_code == model) { + fp->ctf_dmodel = dp; + return (0); + } + } + + return (ctf_set_errno(fp, EINVAL)); +} + +/* + * Return the data model constant for the CTF container. + */ +int +ctf_getmodel(ctf_file_t *fp) +{ + return (fp->ctf_dmodel->ctd_code); +} + +void +ctf_setspecific(ctf_file_t *fp, void *data) +{ + fp->ctf_specific = data; +} + +void * +ctf_getspecific(ctf_file_t *fp) +{ + return (fp->ctf_specific); +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_types.c b/cddl/contrib/opensolaris/common/ctf/ctf_types.c new file mode 100644 index 0000000..290c518 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_types.c @@ -0,0 +1,845 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2006 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <ctf_impl.h> + +ssize_t +ctf_get_ctt_size(const ctf_file_t *fp, const ctf_type_t *tp, ssize_t *sizep, + ssize_t *incrementp) +{ + ssize_t size, increment; + + if (fp->ctf_version > CTF_VERSION_1 && + tp->ctt_size == CTF_LSIZE_SENT) { + size = CTF_TYPE_LSIZE(tp); + increment = sizeof (ctf_type_t); + } else { + size = tp->ctt_size; + increment = sizeof (ctf_stype_t); + } + + if (sizep) + *sizep = size; + if (incrementp) + *incrementp = increment; + + return (size); +} + +/* + * Iterate over the members of a STRUCT or UNION. We pass the name, member + * type, and offset of each member to the specified callback function. + */ +int +ctf_member_iter(ctf_file_t *fp, ctf_id_t type, ctf_member_f *func, void *arg) +{ + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + ssize_t size, increment; + uint_t kind, n; + int rc; + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + (void) ctf_get_ctt_size(fp, tp, &size, &increment); + kind = LCTF_INFO_KIND(fp, tp->ctt_info); + + if (kind != CTF_K_STRUCT && kind != CTF_K_UNION) + return (ctf_set_errno(ofp, ECTF_NOTSOU)); + + if (fp->ctf_version == CTF_VERSION_1 || size < CTF_LSTRUCT_THRESH) { + const ctf_member_t *mp = (const ctf_member_t *) + ((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, mp++) { + const char *name = ctf_strptr(fp, mp->ctm_name); + if ((rc = func(name, mp->ctm_type, mp->ctm_offset, + arg)) != 0) + return (rc); + } + + } else { + const ctf_lmember_t *lmp = (const ctf_lmember_t *) + ((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, lmp++) { + const char *name = ctf_strptr(fp, lmp->ctlm_name); + if ((rc = func(name, lmp->ctlm_type, + (ulong_t)CTF_LMEM_OFFSET(lmp), arg)) != 0) + return (rc); + } + } + + return (0); +} + +/* + * Iterate over the members of an ENUM. We pass the string name and associated + * integer value of each enum element to the specified callback function. + */ +int +ctf_enum_iter(ctf_file_t *fp, ctf_id_t type, ctf_enum_f *func, void *arg) +{ + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + const ctf_enum_t *ep; + ssize_t increment; + uint_t n; + int rc; + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + if (LCTF_INFO_KIND(fp, tp->ctt_info) != CTF_K_ENUM) + return (ctf_set_errno(ofp, ECTF_NOTENUM)); + + (void) ctf_get_ctt_size(fp, tp, NULL, &increment); + + ep = (const ctf_enum_t *)((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, ep++) { + const char *name = ctf_strptr(fp, ep->cte_name); + if ((rc = func(name, ep->cte_value, arg)) != 0) + return (rc); + } + + return (0); +} + +/* + * Iterate over every root (user-visible) type in the given CTF container. + * We pass the type ID of each type to the specified callback function. + */ +int +ctf_type_iter(ctf_file_t *fp, ctf_type_f *func, void *arg) +{ + ctf_id_t id, max = fp->ctf_typemax; + int rc, child = (fp->ctf_flags & LCTF_CHILD); + + for (id = 1; id <= max; id++) { + const ctf_type_t *tp = LCTF_INDEX_TO_TYPEPTR(fp, id); + if (CTF_INFO_ISROOT(tp->ctt_info) && + (rc = func(CTF_INDEX_TO_TYPE(id, child), arg)) != 0) + return (rc); + } + + return (0); +} + +/* + * Follow a given type through the graph for TYPEDEF, VOLATILE, CONST, and + * RESTRICT nodes until we reach a "base" type node. This is useful when + * we want to follow a type ID to a node that has members or a size. To guard + * against infinite loops, we implement simplified cycle detection and check + * each link against itself, the previous node, and the topmost node. + */ +ctf_id_t +ctf_type_resolve(ctf_file_t *fp, ctf_id_t type) +{ + ctf_id_t prev = type, otype = type; + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + + while ((tp = ctf_lookup_by_id(&fp, type)) != NULL) { + switch (LCTF_INFO_KIND(fp, tp->ctt_info)) { + case CTF_K_TYPEDEF: + case CTF_K_VOLATILE: + case CTF_K_CONST: + case CTF_K_RESTRICT: + if (tp->ctt_type == type || tp->ctt_type == otype || + tp->ctt_type == prev) { + ctf_dprintf("type %ld cycle detected\n", otype); + return (ctf_set_errno(ofp, ECTF_CORRUPT)); + } + prev = type; + type = tp->ctt_type; + break; + default: + return (type); + } + } + + return (CTF_ERR); /* errno is set for us */ +} + +/* + * Lookup the given type ID and print a string name for it into buf. Return + * the actual number of bytes (not including \0) needed to format the name. + */ +ssize_t +ctf_type_lname(ctf_file_t *fp, ctf_id_t type, char *buf, size_t len) +{ + ctf_decl_t cd; + ctf_decl_node_t *cdp; + ctf_decl_prec_t prec, lp, rp; + int ptr, arr; + uint_t k; + + if (fp == NULL && type == CTF_ERR) + return (-1); /* simplify caller code by permitting CTF_ERR */ + + ctf_decl_init(&cd, buf, len); + ctf_decl_push(&cd, fp, type); + + if (cd.cd_err != 0) { + ctf_decl_fini(&cd); + return (ctf_set_errno(fp, cd.cd_err)); + } + + /* + * If the type graph's order conflicts with lexical precedence order + * for pointers or arrays, then we need to surround the declarations at + * the corresponding lexical precedence with parentheses. This can + * result in either a parenthesized pointer (*) as in int (*)() or + * int (*)[], or in a parenthesized pointer and array as in int (*[])(). + */ + ptr = cd.cd_order[CTF_PREC_POINTER] > CTF_PREC_POINTER; + arr = cd.cd_order[CTF_PREC_ARRAY] > CTF_PREC_ARRAY; + + rp = arr ? CTF_PREC_ARRAY : ptr ? CTF_PREC_POINTER : -1; + lp = ptr ? CTF_PREC_POINTER : arr ? CTF_PREC_ARRAY : -1; + + k = CTF_K_POINTER; /* avoid leading whitespace (see below) */ + + for (prec = CTF_PREC_BASE; prec < CTF_PREC_MAX; prec++) { + for (cdp = ctf_list_next(&cd.cd_nodes[prec]); + cdp != NULL; cdp = ctf_list_next(cdp)) { + + ctf_file_t *rfp = fp; + const ctf_type_t *tp = + ctf_lookup_by_id(&rfp, cdp->cd_type); + const char *name = ctf_strptr(rfp, tp->ctt_name); + + if (k != CTF_K_POINTER && k != CTF_K_ARRAY) + ctf_decl_sprintf(&cd, " "); + + if (lp == prec) { + ctf_decl_sprintf(&cd, "("); + lp = -1; + } + + switch (cdp->cd_kind) { + case CTF_K_INTEGER: + case CTF_K_FLOAT: + case CTF_K_TYPEDEF: + ctf_decl_sprintf(&cd, "%s", name); + break; + case CTF_K_POINTER: + ctf_decl_sprintf(&cd, "*"); + break; + case CTF_K_ARRAY: + ctf_decl_sprintf(&cd, "[%u]", cdp->cd_n); + break; + case CTF_K_FUNCTION: + ctf_decl_sprintf(&cd, "()"); + break; + case CTF_K_STRUCT: + case CTF_K_FORWARD: + ctf_decl_sprintf(&cd, "struct %s", name); + break; + case CTF_K_UNION: + ctf_decl_sprintf(&cd, "union %s", name); + break; + case CTF_K_ENUM: + ctf_decl_sprintf(&cd, "enum %s", name); + break; + case CTF_K_VOLATILE: + ctf_decl_sprintf(&cd, "volatile"); + break; + case CTF_K_CONST: + ctf_decl_sprintf(&cd, "const"); + break; + case CTF_K_RESTRICT: + ctf_decl_sprintf(&cd, "restrict"); + break; + } + + k = cdp->cd_kind; + } + + if (rp == prec) + ctf_decl_sprintf(&cd, ")"); + } + + if (cd.cd_len >= len) + (void) ctf_set_errno(fp, ECTF_NAMELEN); + + ctf_decl_fini(&cd); + return (cd.cd_len); +} + +/* + * Lookup the given type ID and print a string name for it into buf. If buf + * is too small, return NULL: the ECTF_NAMELEN error is set on 'fp' for us. + */ +char * +ctf_type_name(ctf_file_t *fp, ctf_id_t type, char *buf, size_t len) +{ + ssize_t rv = ctf_type_lname(fp, type, buf, len); + return (rv >= 0 && rv < len ? buf : NULL); +} + +/* + * Resolve the type down to a base type node, and then return the size + * of the type storage in bytes. + */ +ssize_t +ctf_type_size(ctf_file_t *fp, ctf_id_t type) +{ + const ctf_type_t *tp; + ssize_t size; + ctf_arinfo_t ar; + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (-1); /* errno is set for us */ + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (-1); /* errno is set for us */ + + switch (LCTF_INFO_KIND(fp, tp->ctt_info)) { + case CTF_K_POINTER: + return (fp->ctf_dmodel->ctd_pointer); + + case CTF_K_FUNCTION: + return (0); /* function size is only known by symtab */ + + case CTF_K_ENUM: + return (fp->ctf_dmodel->ctd_int); + + case CTF_K_ARRAY: + /* + * Array size is not directly returned by stabs data. Instead, + * it defines the element type and requires the user to perform + * the multiplication. If ctf_get_ctt_size() returns zero, the + * current version of ctfconvert does not compute member sizes + * and we compute the size here on its behalf. + */ + if ((size = ctf_get_ctt_size(fp, tp, NULL, NULL)) > 0) + return (size); + + if (ctf_array_info(fp, type, &ar) == CTF_ERR || + (size = ctf_type_size(fp, ar.ctr_contents)) == CTF_ERR) + return (-1); /* errno is set for us */ + + return (size * ar.ctr_nelems); + + default: + return (ctf_get_ctt_size(fp, tp, NULL, NULL)); + } +} + +/* + * Resolve the type down to a base type node, and then return the alignment + * needed for the type storage in bytes. + */ +ssize_t +ctf_type_align(ctf_file_t *fp, ctf_id_t type) +{ + const ctf_type_t *tp; + ctf_arinfo_t r; + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (-1); /* errno is set for us */ + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (-1); /* errno is set for us */ + + switch (LCTF_INFO_KIND(fp, tp->ctt_info)) { + case CTF_K_POINTER: + case CTF_K_FUNCTION: + return (fp->ctf_dmodel->ctd_pointer); + + case CTF_K_ARRAY: + if (ctf_array_info(fp, type, &r) == CTF_ERR) + return (-1); /* errno is set for us */ + return (ctf_type_align(fp, r.ctr_contents)); + + case CTF_K_STRUCT: + case CTF_K_UNION: { + uint_t n = LCTF_INFO_VLEN(fp, tp->ctt_info); + ssize_t size, increment; + size_t align = 0; + const void *vmp; + + (void) ctf_get_ctt_size(fp, tp, &size, &increment); + vmp = (uchar_t *)tp + increment; + + if (LCTF_INFO_KIND(fp, tp->ctt_info) == CTF_K_STRUCT) + n = MIN(n, 1); /* only use first member for structs */ + + if (fp->ctf_version == CTF_VERSION_1 || + size < CTF_LSTRUCT_THRESH) { + const ctf_member_t *mp = vmp; + for (; n != 0; n--, mp++) { + ssize_t am = ctf_type_align(fp, mp->ctm_type); + align = MAX(align, am); + } + } else { + const ctf_lmember_t *lmp = vmp; + for (; n != 0; n--, lmp++) { + ssize_t am = ctf_type_align(fp, lmp->ctlm_type); + align = MAX(align, am); + } + } + + return (align); + } + + case CTF_K_ENUM: + return (fp->ctf_dmodel->ctd_int); + + default: + return (ctf_get_ctt_size(fp, tp, NULL, NULL)); + } +} + +/* + * Return the kind (CTF_K_* constant) for the specified type ID. + */ +int +ctf_type_kind(ctf_file_t *fp, ctf_id_t type) +{ + const ctf_type_t *tp; + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + return (LCTF_INFO_KIND(fp, tp->ctt_info)); +} + +/* + * If the type is one that directly references another type (such as POINTER), + * then return the ID of the type to which it refers. + */ +ctf_id_t +ctf_type_reference(ctf_file_t *fp, ctf_id_t type) +{ + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + switch (LCTF_INFO_KIND(fp, tp->ctt_info)) { + case CTF_K_POINTER: + case CTF_K_TYPEDEF: + case CTF_K_VOLATILE: + case CTF_K_CONST: + case CTF_K_RESTRICT: + return (tp->ctt_type); + default: + return (ctf_set_errno(ofp, ECTF_NOTREF)); + } +} + +/* + * Find a pointer to type by looking in fp->ctf_ptrtab. If we can't find a + * pointer to the given type, see if we can compute a pointer to the type + * resulting from resolving the type down to its base type and use that + * instead. This helps with cases where the CTF data includes "struct foo *" + * but not "foo_t *" and the user accesses "foo_t *" in the debugger. + */ +ctf_id_t +ctf_type_pointer(ctf_file_t *fp, ctf_id_t type) +{ + ctf_file_t *ofp = fp; + ctf_id_t ntype; + + if (ctf_lookup_by_id(&fp, type) == NULL) + return (CTF_ERR); /* errno is set for us */ + + if ((ntype = fp->ctf_ptrtab[CTF_TYPE_TO_INDEX(type)]) != 0) + return (CTF_INDEX_TO_TYPE(ntype, (fp->ctf_flags & LCTF_CHILD))); + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (ctf_set_errno(ofp, ECTF_NOTYPE)); + + if (ctf_lookup_by_id(&fp, type) == NULL) + return (ctf_set_errno(ofp, ECTF_NOTYPE)); + + if ((ntype = fp->ctf_ptrtab[CTF_TYPE_TO_INDEX(type)]) != 0) + return (CTF_INDEX_TO_TYPE(ntype, (fp->ctf_flags & LCTF_CHILD))); + + return (ctf_set_errno(ofp, ECTF_NOTYPE)); +} + +/* + * Return the encoding for the specified INTEGER or FLOAT. + */ +int +ctf_type_encoding(ctf_file_t *fp, ctf_id_t type, ctf_encoding_t *ep) +{ + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + ssize_t increment; + uint_t data; + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + (void) ctf_get_ctt_size(fp, tp, NULL, &increment); + + switch (LCTF_INFO_KIND(fp, tp->ctt_info)) { + case CTF_K_INTEGER: + data = *(const uint_t *)((uintptr_t)tp + increment); + ep->cte_format = CTF_INT_ENCODING(data); + ep->cte_offset = CTF_INT_OFFSET(data); + ep->cte_bits = CTF_INT_BITS(data); + break; + case CTF_K_FLOAT: + data = *(const uint_t *)((uintptr_t)tp + increment); + ep->cte_format = CTF_FP_ENCODING(data); + ep->cte_offset = CTF_FP_OFFSET(data); + ep->cte_bits = CTF_FP_BITS(data); + break; + default: + return (ctf_set_errno(ofp, ECTF_NOTINTFP)); + } + + return (0); +} + +int +ctf_type_cmp(ctf_file_t *lfp, ctf_id_t ltype, ctf_file_t *rfp, ctf_id_t rtype) +{ + int rval; + + if (ltype < rtype) + rval = -1; + else if (ltype > rtype) + rval = 1; + else + rval = 0; + + if (lfp == rfp) + return (rval); + + if (CTF_TYPE_ISPARENT(ltype) && lfp->ctf_parent != NULL) + lfp = lfp->ctf_parent; + + if (CTF_TYPE_ISPARENT(rtype) && rfp->ctf_parent != NULL) + rfp = rfp->ctf_parent; + + if (lfp < rfp) + return (-1); + + if (lfp > rfp) + return (1); + + return (rval); +} + +/* + * Return a boolean value indicating if two types are compatible integers or + * floating-pointer values. This function returns true if the two types are + * the same, or if they have the same ASCII name and encoding properties. + * This function could be extended to test for compatibility for other kinds. + */ +int +ctf_type_compat(ctf_file_t *lfp, ctf_id_t ltype, + ctf_file_t *rfp, ctf_id_t rtype) +{ + const ctf_type_t *ltp, *rtp; + ctf_encoding_t le, re; + ctf_arinfo_t la, ra; + uint_t lkind, rkind; + + if (ctf_type_cmp(lfp, ltype, rfp, rtype) == 0) + return (1); + + ltype = ctf_type_resolve(lfp, ltype); + lkind = ctf_type_kind(lfp, ltype); + + rtype = ctf_type_resolve(rfp, rtype); + rkind = ctf_type_kind(rfp, rtype); + + if (lkind != rkind || + (ltp = ctf_lookup_by_id(&lfp, ltype)) == NULL || + (rtp = ctf_lookup_by_id(&rfp, rtype)) == NULL || + strcmp(ctf_strptr(lfp, ltp->ctt_name), + ctf_strptr(rfp, rtp->ctt_name)) != 0) + return (0); + + switch (lkind) { + case CTF_K_INTEGER: + case CTF_K_FLOAT: + return (ctf_type_encoding(lfp, ltype, &le) == 0 && + ctf_type_encoding(rfp, rtype, &re) == 0 && + bcmp(&le, &re, sizeof (ctf_encoding_t)) == 0); + case CTF_K_POINTER: + return (ctf_type_compat(lfp, ctf_type_reference(lfp, ltype), + rfp, ctf_type_reference(rfp, rtype))); + case CTF_K_ARRAY: + return (ctf_array_info(lfp, ltype, &la) == 0 && + ctf_array_info(rfp, rtype, &ra) == 0 && + la.ctr_nelems == ra.ctr_nelems && ctf_type_compat( + lfp, la.ctr_contents, rfp, ra.ctr_contents) && + ctf_type_compat(lfp, la.ctr_index, rfp, ra.ctr_index)); + case CTF_K_STRUCT: + case CTF_K_UNION: + return (ctf_type_size(lfp, ltype) == ctf_type_size(rfp, rtype)); + case CTF_K_ENUM: + case CTF_K_FORWARD: + return (1); /* no other checks required for these type kinds */ + default: + return (0); /* should not get here since we did a resolve */ + } +} + +/* + * Return the type and offset for a given member of a STRUCT or UNION. + */ +int +ctf_member_info(ctf_file_t *fp, ctf_id_t type, const char *name, + ctf_membinfo_t *mip) +{ + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + ssize_t size, increment; + uint_t kind, n; + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + (void) ctf_get_ctt_size(fp, tp, &size, &increment); + kind = LCTF_INFO_KIND(fp, tp->ctt_info); + + if (kind != CTF_K_STRUCT && kind != CTF_K_UNION) + return (ctf_set_errno(ofp, ECTF_NOTSOU)); + + if (fp->ctf_version == CTF_VERSION_1 || size < CTF_LSTRUCT_THRESH) { + const ctf_member_t *mp = (const ctf_member_t *) + ((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, mp++) { + if (strcmp(ctf_strptr(fp, mp->ctm_name), name) == 0) { + mip->ctm_type = mp->ctm_type; + mip->ctm_offset = mp->ctm_offset; + return (0); + } + } + } else { + const ctf_lmember_t *lmp = (const ctf_lmember_t *) + ((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, lmp++) { + if (strcmp(ctf_strptr(fp, lmp->ctlm_name), name) == 0) { + mip->ctm_type = lmp->ctlm_type; + mip->ctm_offset = (ulong_t)CTF_LMEM_OFFSET(lmp); + return (0); + } + } + } + + return (ctf_set_errno(ofp, ECTF_NOMEMBNAM)); +} + +/* + * Return the array type, index, and size information for the specified ARRAY. + */ +int +ctf_array_info(ctf_file_t *fp, ctf_id_t type, ctf_arinfo_t *arp) +{ + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + const ctf_array_t *ap; + ssize_t increment; + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + if (LCTF_INFO_KIND(fp, tp->ctt_info) != CTF_K_ARRAY) + return (ctf_set_errno(ofp, ECTF_NOTARRAY)); + + (void) ctf_get_ctt_size(fp, tp, NULL, &increment); + + ap = (const ctf_array_t *)((uintptr_t)tp + increment); + arp->ctr_contents = ap->cta_contents; + arp->ctr_index = ap->cta_index; + arp->ctr_nelems = ap->cta_nelems; + + return (0); +} + +/* + * Convert the specified value to the corresponding enum member name, if a + * matching name can be found. Otherwise NULL is returned. + */ +const char * +ctf_enum_name(ctf_file_t *fp, ctf_id_t type, int value) +{ + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + const ctf_enum_t *ep; + ssize_t increment; + uint_t n; + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (NULL); /* errno is set for us */ + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (NULL); /* errno is set for us */ + + if (LCTF_INFO_KIND(fp, tp->ctt_info) != CTF_K_ENUM) { + (void) ctf_set_errno(ofp, ECTF_NOTENUM); + return (NULL); + } + + (void) ctf_get_ctt_size(fp, tp, NULL, &increment); + + ep = (const ctf_enum_t *)((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, ep++) { + if (ep->cte_value == value) + return (ctf_strptr(fp, ep->cte_name)); + } + + (void) ctf_set_errno(ofp, ECTF_NOENUMNAM); + return (NULL); +} + +/* + * Convert the specified enum tag name to the corresponding value, if a + * matching name can be found. Otherwise CTF_ERR is returned. + */ +int +ctf_enum_value(ctf_file_t *fp, ctf_id_t type, const char *name, int *valp) +{ + ctf_file_t *ofp = fp; + const ctf_type_t *tp; + const ctf_enum_t *ep; + ssize_t size, increment; + uint_t n; + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + if (LCTF_INFO_KIND(fp, tp->ctt_info) != CTF_K_ENUM) { + (void) ctf_set_errno(ofp, ECTF_NOTENUM); + return (CTF_ERR); + } + + (void) ctf_get_ctt_size(fp, tp, &size, &increment); + + ep = (const ctf_enum_t *)((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, ep++) { + if (strcmp(ctf_strptr(fp, ep->cte_name), name) == 0) { + if (valp != NULL) + *valp = ep->cte_value; + return (0); + } + } + + (void) ctf_set_errno(ofp, ECTF_NOENUMNAM); + return (CTF_ERR); +} + +/* + * Recursively visit the members of any type. This function is used as the + * engine for ctf_type_visit, below. We resolve the input type, recursively + * invoke ourself for each type member if the type is a struct or union, and + * then invoke the callback function on the current type. If any callback + * returns non-zero, we abort and percolate the error code back up to the top. + */ +static int +ctf_type_rvisit(ctf_file_t *fp, ctf_id_t type, ctf_visit_f *func, void *arg, + const char *name, ulong_t offset, int depth) +{ + ctf_id_t otype = type; + const ctf_type_t *tp; + ssize_t size, increment; + uint_t kind, n; + int rc; + + if ((type = ctf_type_resolve(fp, type)) == CTF_ERR) + return (CTF_ERR); /* errno is set for us */ + + if ((tp = ctf_lookup_by_id(&fp, type)) == NULL) + return (CTF_ERR); /* errno is set for us */ + + if ((rc = func(name, otype, offset, depth, arg)) != 0) + return (rc); + + kind = LCTF_INFO_KIND(fp, tp->ctt_info); + + if (kind != CTF_K_STRUCT && kind != CTF_K_UNION) + return (0); + + (void) ctf_get_ctt_size(fp, tp, &size, &increment); + + if (fp->ctf_version == CTF_VERSION_1 || size < CTF_LSTRUCT_THRESH) { + const ctf_member_t *mp = (const ctf_member_t *) + ((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, mp++) { + if ((rc = ctf_type_rvisit(fp, mp->ctm_type, + func, arg, ctf_strptr(fp, mp->ctm_name), + offset + mp->ctm_offset, depth + 1)) != 0) + return (rc); + } + + } else { + const ctf_lmember_t *lmp = (const ctf_lmember_t *) + ((uintptr_t)tp + increment); + + for (n = LCTF_INFO_VLEN(fp, tp->ctt_info); n != 0; n--, lmp++) { + if ((rc = ctf_type_rvisit(fp, lmp->ctlm_type, + func, arg, ctf_strptr(fp, lmp->ctlm_name), + offset + (ulong_t)CTF_LMEM_OFFSET(lmp), + depth + 1)) != 0) + return (rc); + } + } + + return (0); +} + +/* + * Recursively visit the members of any type. We pass the name, member + * type, and offset of each member to the specified callback function. + */ +int +ctf_type_visit(ctf_file_t *fp, ctf_id_t type, ctf_visit_f *func, void *arg) +{ + return (ctf_type_rvisit(fp, type, func, arg, "", 0, 0)); +} diff --git a/cddl/contrib/opensolaris/common/ctf/ctf_util.c b/cddl/contrib/opensolaris/common/ctf/ctf_util.c new file mode 100644 index 0000000..740d403 --- /dev/null +++ b/cddl/contrib/opensolaris/common/ctf/ctf_util.c @@ -0,0 +1,152 @@ +/* + * CDDL HEADER START + * + * The contents of this file are subject to the terms of the + * Common Development and Distribution License, Version 1.0 only + * (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 2005 Sun Microsystems, Inc. All rights reserved. + * Use is subject to license terms. + */ + +#pragma ident "%Z%%M% %I% %E% SMI" + +#include <ctf_impl.h> + +/* + * Simple doubly-linked list append routine. This implementation assumes that + * each list element contains an embedded ctf_list_t as the first member. + * An additional ctf_list_t is used to store the head (l_next) and tail + * (l_prev) pointers. The current head and tail list elements have their + * previous and next pointers set to NULL, respectively. + */ +void +ctf_list_append(ctf_list_t *lp, void *new) +{ + ctf_list_t *p = lp->l_prev; /* p = tail list element */ + ctf_list_t *q = new; /* q = new list element */ + + lp->l_prev = q; + q->l_prev = p; + q->l_next = NULL; + + if (p != NULL) + p->l_next = q; + else + lp->l_next = q; +} + +/* + * Prepend the specified existing element to the given ctf_list_t. The + * existing pointer should be pointing at a struct with embedded ctf_list_t. + */ +void +ctf_list_prepend(ctf_list_t *lp, void *new) +{ + ctf_list_t *p = new; /* p = new list element */ + ctf_list_t *q = lp->l_next; /* q = head list element */ + + lp->l_next = p; + p->l_prev = NULL; + p->l_next = q; + + if (q != NULL) + q->l_prev = p; + else + lp->l_prev = p; +} + +/* + * Delete the specified existing element from the given ctf_list_t. The + * existing pointer should be pointing at a struct with embedded ctf_list_t. + */ +void +ctf_list_delete(ctf_list_t *lp, void *existing) +{ + ctf_list_t *p = existing; + + if (p->l_prev != NULL) + p->l_prev->l_next = p->l_next; + else + lp->l_next = p->l_next; + + if (p->l_next != NULL) + p->l_next->l_prev = p->l_prev; + else + lp->l_prev = p->l_prev; +} + +/* + * Convert an encoded CTF string name into a pointer to a C string by looking + * up the appropriate string table buffer and then adding the offset. + */ +const char * +ctf_strraw(ctf_file_t *fp, uint_t name) +{ + ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID(name)]; + + if (ctsp->cts_strs != NULL && CTF_NAME_OFFSET(name) < ctsp->cts_len) + return (ctsp->cts_strs + CTF_NAME_OFFSET(name)); + + /* string table not loaded or corrupt offset */ + return (NULL); +} + +const char * +ctf_strptr(ctf_file_t *fp, uint_t name) +{ + const char *s = ctf_strraw(fp, name); + return (s != NULL ? s : "(?)"); +} + +/* + * Same strdup(3C), but use ctf_alloc() to do the memory allocation. + */ +char * +ctf_strdup(const char *s1) +{ + char *s2 = ctf_alloc(strlen(s1) + 1); + + if (s2 != NULL) + (void) strcpy(s2, s1); + + return (s2); +} + +/* + * Store the specified error code into errp if it is non-NULL, and then + * return NULL for the benefit of the caller. + */ +ctf_file_t * +ctf_set_open_errno(int *errp, int error) +{ + if (errp != NULL) + *errp = error; + return (NULL); +} + +/* + * Store the specified error code into the CTF container, and then return + * CTF_ERR for the benefit of the caller. + */ +long +ctf_set_errno(ctf_file_t *fp, int err) +{ + fp->ctf_errno = err; + return (CTF_ERR); +} |
