1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 /*
27  * Copyright 2019 Joyent, Inc.
28  */
29 
30 #include <string.h>
31 #include <unistd.h>
32 #include <assert.h>
33 
34 #include <topo_error.h>
35 #include <topo_list.h>
36 #include <topo_tree.h>
37 
38 /*
39  * Embedded Linked Lists
40  *
41  * Simple doubly-linked list implementation.  This implementation assumes that
42  * each list element contains an embedded topo_list_t (previous and next
43  * pointers), which is typically the first member of the element struct.
44  * An additional topo_list_t is used to store the head (l_next) and tail
45  * (l_prev) pointers.  The current head and tail list elements have their
46  * previous and next pointers set to NULL, respectively.
47  *
48  * NOTE: The embeddable list code in this file intentionally provides no
49  * locking of any kind.  The implementation of any list in topo must provide
50  * an appropriate locking strategy to protect the list or to protect access
51  * to the embedded topo_list_t inside of each list element to avoid corruption.
52  * Refer to comments in the source files that use topo_list_t for lock details.
53  */
54 
55 
56 void
topo_list_append(topo_list_t * lp,void * new)57 topo_list_append(topo_list_t *lp, void *new)
58 {
59 	topo_list_t *p = lp->l_prev;	/* p = tail list element */
60 	topo_list_t *q = new;		/* q = new list element */
61 
62 	lp->l_prev = q;
63 	q->l_prev = p;
64 	q->l_next = NULL;
65 
66 	if (p != NULL) {
67 		assert(p->l_next == NULL);
68 		p->l_next = q;
69 	} else {
70 		assert(lp->l_next == NULL);
71 		lp->l_next = q;
72 	}
73 }
74 
75 void
topo_list_prepend(topo_list_t * lp,void * new)76 topo_list_prepend(topo_list_t *lp, void *new)
77 {
78 	topo_list_t *p = new;		/* p = new list element */
79 	topo_list_t *q = lp->l_next;	/* q = head list element */
80 
81 	lp->l_next = p;
82 	p->l_prev = NULL;
83 	p->l_next = q;
84 
85 	if (q != NULL) {
86 		assert(q->l_prev == NULL);
87 		q->l_prev = p;
88 	} else {
89 		assert(lp->l_prev == NULL);
90 		lp->l_prev = p;
91 	}
92 }
93 
94 void
topo_list_insert_before(topo_list_t * lp,void * before_me,void * new)95 topo_list_insert_before(topo_list_t *lp, void *before_me, void *new)
96 {
97 	topo_list_t *p = before_me;
98 	topo_list_t *q = new;
99 
100 	if (p == NULL || p->l_prev == NULL) {
101 		topo_list_prepend(lp, new);
102 		return;
103 	}
104 
105 	q->l_prev = p->l_prev;
106 	q->l_next = p;
107 	p->l_prev = q;
108 	q->l_prev->l_next = q;
109 }
110 
111 void
topo_list_insert_after(topo_list_t * lp,void * after_me,void * new)112 topo_list_insert_after(topo_list_t *lp, void *after_me, void *new)
113 {
114 	topo_list_t *p = after_me;
115 	topo_list_t *q = new;
116 
117 	if (p == NULL || p->l_next == NULL) {
118 		topo_list_append(lp, new);
119 		return;
120 	}
121 
122 	q->l_next = p->l_next;
123 	q->l_prev = p;
124 	p->l_next = q;
125 	q->l_next->l_prev = q;
126 }
127 
128 void
topo_list_delete(topo_list_t * lp,void * existing)129 topo_list_delete(topo_list_t *lp, void *existing)
130 {
131 	topo_list_t *p = existing;
132 
133 	if (p->l_prev != NULL)
134 		p->l_prev->l_next = p->l_next;
135 	else
136 		lp->l_next = p->l_next;
137 
138 	if (p->l_next != NULL)
139 		p->l_next->l_prev = p->l_prev;
140 	else
141 		lp->l_prev = p->l_prev;
142 }
143 
144 tnode_t *
topo_child_first(tnode_t * pnode)145 topo_child_first(tnode_t *pnode)
146 {
147 	int i;
148 	topo_nodehash_t *nhp;
149 
150 	for (nhp = topo_list_next(&pnode->tn_children); nhp != NULL;
151 	    nhp = topo_list_next(nhp)) {
152 		for (i = 0; i < nhp->th_arrlen; ++i) {
153 			if (nhp->th_nodearr[i] != NULL)
154 				return (nhp->th_nodearr[i]);
155 		}
156 	}
157 
158 	return (NULL);
159 }
160 
161 tnode_t *
topo_child_next(tnode_t * pnode,tnode_t * node)162 topo_child_next(tnode_t *pnode, tnode_t *node)
163 {
164 	int i;
165 	int index;
166 	topo_nodehash_t *nhp;
167 
168 	if (node == NULL) {
169 		return (topo_child_first(pnode));
170 	}
171 
172 	/*
173 	 * Begin search for next child in the current hash array
174 	 * If none found or we are at the end of the array, move
175 	 * on to the next array
176 	 */
177 	index = topo_node_hash(node->tn_phash, node->tn_instance) + 1;
178 	for (nhp = node->tn_phash; nhp != NULL; nhp = topo_list_next(nhp)) {
179 		for (i = index; i < nhp->th_arrlen; ++i) {
180 			if (nhp->th_nodearr[i] != NULL) {
181 				return (nhp->th_nodearr[i]);
182 			}
183 		}
184 		index = 0;
185 	}
186 
187 	return (NULL);
188 }
189 
190 int
topo_list_deepcopy(topo_hdl_t * thp,topo_list_t * dest,topo_list_t * src,size_t elem_sz)191 topo_list_deepcopy(topo_hdl_t *thp, topo_list_t *dest, topo_list_t *src,
192     size_t elem_sz)
193 {
194 	void *elem;
195 
196 	/* if the destination list is not empty - bail out */
197 	if (topo_list_next(dest) != NULL)
198 		return (topo_hdl_seterrno(thp, ETOPO_UNKNOWN));
199 
200 	for (elem = topo_list_next(src); elem != NULL;
201 	    elem = topo_list_next(elem)) {
202 		void *elem_copy;
203 
204 		if ((elem_copy = topo_hdl_alloc(thp, elem_sz)) == NULL) {
205 			goto err;
206 		}
207 		(void) memcpy(elem_copy, elem, elem_sz);
208 		topo_list_append(dest, elem_copy);
209 	}
210 	return (0);
211 
212 err:
213 	/*
214 	 * If we hit an error, cleanup any partially copied list elements
215 	 * before we return.
216 	 */
217 	elem = topo_list_next(dest);
218 	while (elem != NULL) {
219 		void *tmp = elem;
220 
221 		elem = topo_list_next(elem);
222 		topo_list_delete(dest, tmp);
223 		topo_hdl_free(thp, tmp, elem_sz);
224 	}
225 	return (topo_hdl_seterrno(thp, ETOPO_NOMEM));
226 }
227