During my 10+ years at Sun, I've had the privilege of working with the Solaris Printing group much of the time. During my IT days, I worked worked closely with the OS engineers during development of Solaris 2.6 operating environment, ensuring we ran with new bits on individual workstations and servers. It was during this timeframe that I began working with the Solaris Printing group, working to run the latest and greatest bits on building print servers. Solaris printing has evolved tremendously since then. So many additions that have made the installation and setup of printing so much simpler. Instead of talking about anything specific in Solaris Printing right now though, and as both printing and the developers who work on it are very near and dear to my heart, I just wanted to point out the OpenSolaris Printing Community page which contains oodles of information. Make sure to check it out!

The Single UNIX Specification Version 3 (SUSv3) included requirements for various utilities to support traversal of file hierarchies. When implementing these traversal requirements, it became apparent that a method to track inodes visited/processed while traversing a file hierarchy was necessary in order to detect endless loops. This inode information needs to be saved in the following cases:

• if the inode is a directory. Why? Because a hard link to a directory may exist which could lead to an endless loop.
• if the option to "follow symlinks" was also specified. Why? Because we do not know if the inode being processed is a file referenced by a symlink, thus may lead to an endless loop.

When we process an inode, we check to see if it's already been visited by searching previously saved inode information for a matching device id and inode number. If so, a loop has been detected, and we can break out of processing that portion of the hierarchy. If not, we simply add the inode's information to the list of inodes visited, and continue.

My first thought was to use a linked list to manage the visited inode's information as some of the commands already had this support built in. However, as the amount of data increases, this linear approach becomes inefficient.

It just so happened that Joe Bonasera developed a very generic set of AVL (Addison-Velski and Landis) tree routines for the Solaris kernel, providing a useful alternative to linked lists (or btrees). Joe did the hard work. All I needed to do was to reuse the functionality by making these interfaces available to user-level implementations. Thus, the AVL tree library (libavl) was created with the following interfaces (see usr/src/uts/common/sys/avl.h, as Joe did an excellent job of documenting it):

avl_create()
avl_destroy()
avl_destroy_nodes()
avl_first()
avl_last()
avl_find()
avl_insert()
avl_nearest()
avl_numnodes()
avl_remove()
AVL_NEXT()
AVL_PREV()

libavl was delivered as a private library, however, if there is enough interest in making it public, that could easily be done.

I also added a few routines to a separate private library (libcmdutils) to complement the interfaces available in libavl as each of the utilities I was adding traversal support to needed a common set of routines:

tnode_compare() - Tree node comparison routines
add_tnode() - Add a node to the AVL tree
destroy_tree() - Destroy the whole AVL tree (all nodes) without rebalancing.

The following structure, tree_node_t, was included to enable to saving/searching on an inode's device id and inode number:

typedef struct tree_node {
        dev_t           node_dev;
        ino_t           node_ino;
        avl_node_t      avl_link;
} tree_node_t;

Here's an example, taken from usr/src/cmd/du/du.c, of how an AVL search tree is used to maintain the device id and inode number for each inode visited:

#include 

[...]

static avl_tree_t       *tree = NULL;

[...]
        /*
         * If following links (-L) we need to keep track of all inodes
         * visited so they are only visited/reported once and cycles
         * are avoided.  Otherwise, only keep track of files which are
         * hard links so they only get reported once, and of directories
         * so we don't report a directory and its hierarchy more than
         * once in the special case in which it lies under the
         * hierarchy of a directory which is a hard link.
         * Note:  Files with multiple links should only be counted
         * once.  Since each inode could possibly be referenced by a
         * symbolic link, we need to keep track of all inodes when -L
         * is specified.
         */
        if ((Lflg) || ((stb.st_mode & S_IFMT) == S_IFDIR) ||
            (stb.st_nlink > 1)) {
                int rc;
                if ((rc = add_tnode(&tree, stb.st_dev, stb.st_ino)) != 1) {
                        if (rc == 0) {
                                /*
                                 * This hierarchy, or file with multiple
                                 * links, has already been visited/reported.
                                 */
                                return (0);
                        } else {
                                /*
                                 * An error occurred while trying to add the
                                 * node to the tree.
                                 */
                                if (rflg) {
                                        perror("du");
                                }
                                exitdu(1);
                        }
                }
        }
[...]

Befitting text for a first blog, don’t you think? :)

With as much as I like to talk, you’d think I would have started blogging long ago. I’m one who normally likes face-to-face personal interaction, so this blogging thing is a new venture for me.

So, let me begin by telling you a bit about myself and my role at Sun. I’ve been at Sun for a little over 10 years, where I’ve worn several hats. I started at Sun as a system administrator, moved to the Solaris Printing group, and most recently, I am working in the Solaris Commands and Utilities group. I should add that I still have the privilege of bouncing into the Solaris Printing group as I’m allowed the pleasure of participating in both areas. I’ve been so blessed working with such wonderful, remarkably talented, and extremely supportive people all along the way.

On the personal side… Well, I try to stay active. I’m on a volleyball team, first established in my ole “Big Blue” days, with some of my dearest friends who helped me to transition to life in sunny California. And, can you imagine, I also bowl! For 3 or 4 years now, with some of my volleyball teammates, significant others, and extended set of friends, I’ve been on a very successful bowling team. In fact, to brag just a bit, we just took 1st place in our league. I received (actually, will receive, as the awards banquet is on June 18) an award for high series (for women)!

I absolutely love the Sun environment and the many fantastic people that I work with every day. It's exciting starting on this path to blogging my thoughts and tidbits about the projects and work I'm doing. Again, hello world! and stay tuned.