1 /*
2  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
3  * Use is subject to license terms.
4  */
5 
6 
7 /*
8  * prof_tree.c --- these routines maintain the parse tree of the
9  * 	config file.
10  *
11  * All of the details of how the tree is stored is abstracted away in
12  * this file; all of the other profile routines build, access, and
13  * modify the tree via the accessor functions found in this file.
14  *
15  * Each node may represent either a relation or a section header.
16  *
17  * A section header must have its value field set to 0, and may a one
18  * or more child nodes, pointed to by first_child.
19  *
20  * A relation has as its value a pointer to allocated memory
21  * containing a string.  Its first_child pointer must be null.
22  *
23  */
24 
25 
26 #include "prof_int.h"
27 
28 #include <stdio.h>
29 #include <string.h>
30 #ifdef HAVE_STDLIB_H
31 #include <stdlib.h>
32 #endif
33 #include <errno.h>
34 #include <ctype.h>
35 
36 struct profile_node {
37 	errcode_t	magic;
38 	char *name;
39 	char *value;
40 	int group_level;
41 	int final:1;		/* Indicate don't search next file */
42 	int deleted:1;
43 	struct profile_node *first_child;
44 	struct profile_node *parent;
45 	struct profile_node *next, *prev;
46 };
47 
48 #define CHECK_MAGIC(node) \
49 	  if ((node)->magic != PROF_MAGIC_NODE) \
50 		  return PROF_MAGIC_NODE;
51 
52 /*
53  * Free a node, and any children
54  */
profile_free_node(struct profile_node * node)55 void profile_free_node(struct profile_node *node)
56 {
57 	struct profile_node *child, *next;
58 
59 	if (node->magic != PROF_MAGIC_NODE)
60 		return;
61 
62 	if (node->name)
63 		free(node->name);
64 	if (node->value)
65 		free(node->value);
66 
67 	for (child=node->first_child; child; child = next) {
68 		next = child->next;
69 		profile_free_node(child);
70 	}
71 	node->magic = 0;
72 
73 	free(node);
74 }
75 
76 #ifndef HAVE_STRDUP
77 #undef strdup
78 #define strdup MYstrdup
MYstrdup(const char * s)79 static char *MYstrdup (const char *s)
80 {
81     size_t sz = strlen(s) + 1;
82     char *p = malloc(sz);
83     if (p != 0)
84 	memcpy(p, s, sz);
85     return p;
86 }
87 #endif
88 
89 /*
90  * Create a node
91  */
profile_create_node(const char * name,const char * value,struct profile_node ** ret_node)92 errcode_t profile_create_node(const char *name, const char *value,
93 			      struct profile_node **ret_node)
94 {
95 	struct profile_node *new;
96 
97 	new = malloc(sizeof(struct profile_node));
98 	if (!new)
99 		return ENOMEM;
100 	memset(new, 0, sizeof(struct profile_node));
101 	new->name = strdup(name);
102 	if (new->name == 0) {
103 	    profile_free_node(new);
104 	    return ENOMEM;
105 	}
106 	if (value) {
107 		new->value = strdup(value);
108 		if (new->value == 0) {
109 		    profile_free_node(new);
110 		    return ENOMEM;
111 		}
112 	}
113 	new->magic = PROF_MAGIC_NODE;
114 
115 	*ret_node = new;
116 	return 0;
117 }
118 
119 /*
120  * This function verifies that all of the representation invarients of
121  * the profile are true.  If not, we have a programming bug somewhere,
122  * probably in this file.
123  */
profile_verify_node(struct profile_node * node)124 errcode_t profile_verify_node(struct profile_node *node)
125 {
126 	struct profile_node *p, *last;
127 	errcode_t	retval;
128 
129 	CHECK_MAGIC(node);
130 
131 	if (node->value && node->first_child)
132 		return PROF_SECTION_WITH_VALUE;
133 
134 	last = 0;
135 	for (p = node->first_child; p; last = p, p = p->next) {
136 		if (p->prev != last)
137 			return PROF_BAD_LINK_LIST;
138 		if (last && (last->next != p))
139 			return PROF_BAD_LINK_LIST;
140 		if (node->group_level+1 != p->group_level)
141 			return PROF_BAD_GROUP_LVL;
142 		if (p->parent != node)
143 			return PROF_BAD_PARENT_PTR;
144 		retval = profile_verify_node(p);
145 		if (retval)
146 			return retval;
147 	}
148 	return 0;
149 }
150 
151 /*
152  * Add a node to a particular section
153  */
profile_add_node(struct profile_node * section,const char * name,const char * value,struct profile_node ** ret_node)154 errcode_t profile_add_node(struct profile_node *section, const char *name,
155 			   const char *value, struct profile_node **ret_node)
156 {
157 	errcode_t retval;
158 	struct profile_node *p, *last, *new;
159 
160 	CHECK_MAGIC(section);
161 
162 	if (section->value)
163 		return PROF_ADD_NOT_SECTION;
164 
165 	/*
166 	 * Find the place to insert the new node.  We look for the
167 	 * place *after* the last match of the node name, since
168 	 * order matters.
169 	 */
170 	for (p=section->first_child, last = 0; p; last = p, p = p->next) {
171 		int cmp;
172 		cmp = strcmp(p->name, name);
173 		if (cmp > 0)
174 			break;
175 	}
176 	retval = profile_create_node(name, value, &new);
177 	if (retval)
178 		return retval;
179 	new->group_level = section->group_level+1;
180 	new->deleted = 0;
181 	new->parent = section;
182 	new->prev = last;
183 	new->next = p;
184 	if (p)
185 		p->prev = new;
186 	if (last)
187 		last->next = new;
188 	else
189 		section->first_child = new;
190 	if (ret_node)
191 		*ret_node = new;
192 	return 0;
193 }
194 
195 /*
196  * Set the final flag on a particular node.
197  */
profile_make_node_final(struct profile_node * node)198 errcode_t profile_make_node_final(struct profile_node *node)
199 {
200 	CHECK_MAGIC(node);
201 
202 	node->final = 1;
203 	return 0;
204 }
205 
206 /*
207  * Check the final flag on a node
208  */
profile_is_node_final(struct profile_node * node)209 int profile_is_node_final(struct profile_node *node)
210 {
211 	return (node->final != 0);
212 }
213 
214 /*
215  * Return the name of a node.  (Note: this is for internal functions
216  * only; if the name needs to be returned from an exported function,
217  * strdup it first!)
218  */
profile_get_node_name(struct profile_node * node)219 const char *profile_get_node_name(struct profile_node *node)
220 {
221 	return node->name;
222 }
223 
224 /*
225  * Return the value of a node.  (Note: this is for internal functions
226  * only; if the name needs to be returned from an exported function,
227  * strdup it first!)
228  */
profile_get_node_value(struct profile_node * node)229 const char *profile_get_node_value(struct profile_node *node)
230 {
231 	return node->value;
232 }
233 
234 /*
235  * Iterate through the section, returning the nodes which match
236  * the given name.  If name is NULL, then interate through all the
237  * nodes in the section.  If section_flag is non-zero, only return the
238  * section which matches the name; don't return relations.  If value
239  * is non-NULL, then only return relations which match the requested
240  * value.  (The value argument is ignored if section_flag is non-zero.)
241  *
242  * The first time this routine is called, the state pointer must be
243  * null.  When this profile_find_node_relation() returns, if the state
244  * pointer is non-NULL, then this routine should be called again.
245  * (This won't happen if section_flag is non-zero, obviously.)
246  *
247  */
profile_find_node(struct profile_node * section,const char * name,const char * value,int section_flag,void ** state,struct profile_node ** node)248 errcode_t profile_find_node(struct profile_node *section, const char *name,
249 			    const char *value, int section_flag, void **state,
250 			    struct profile_node **node)
251 {
252 	struct profile_node *p;
253 
254 	CHECK_MAGIC(section);
255 	p = *state;
256 	if (p) {
257 		CHECK_MAGIC(p);
258 	} else
259 		p = section->first_child;
260 
261 	for (; p; p = p->next) {
262 		if (name && (strcmp(p->name, name)))
263 			continue;
264 		if (section_flag) {
265 			if (p->value)
266 				continue;
267 		} else {
268 			if (!p->value)
269 				continue;
270 			if (value && (strcmp(p->value, value)))
271 				continue;
272 		}
273 		if (p->deleted)
274 		    continue;
275 		/* A match! */
276 		if (node)
277 			*node = p;
278 		break;
279 	}
280 	if (p == 0) {
281 		*state = 0;
282 		return section_flag ? PROF_NO_SECTION : PROF_NO_RELATION;
283 	}
284 	/*
285 	 * OK, we've found one match; now let's try to find another
286 	 * one.  This way, if we return a non-zero state pointer,
287 	 * there's guaranteed to be another match that's returned.
288 	 */
289 	for (p = p->next; p; p = p->next) {
290 		if (name && (strcmp(p->name, name)))
291 			continue;
292 		if (section_flag) {
293 			if (p->value)
294 				continue;
295 		} else {
296 			if (!p->value)
297 				continue;
298 			if (value && (strcmp(p->value, value)))
299 				continue;
300 		}
301 		/* A match! */
302 		break;
303 	}
304 	*state = p;
305 	return 0;
306 }
307 
308 
309 /*
310  * Iterate through the section, returning the relations which match
311  * the given name.  If name is NULL, then interate through all the
312  * relations in the section.  The first time this routine is called,
313  * the state pointer must be null.  When this profile_find_node_relation()
314  * returns, if the state pointer is non-NULL, then this routine should
315  * be called again.
316  *
317  * The returned character string in value points to the stored
318  * character string in the parse string.  Before this string value is
319  * returned to a calling application (profile_find_node_relation is not an
320  * exported interface), it should be strdup()'ed.
321  */
profile_find_node_relation(struct profile_node * section,const char * name,void ** state,char ** ret_name,char ** value)322 errcode_t profile_find_node_relation(struct profile_node *section,
323 				     const char *name, void **state,
324 				     char **ret_name, char **value)
325 {
326 	struct profile_node *p;
327 	errcode_t	retval;
328 
329 	retval = profile_find_node(section, name, 0, 0, state, &p);
330 	if (retval)
331 		return retval;
332 
333 	if (p) {
334 		if (value)
335 			*value = p->value;
336 		if (ret_name)
337 			*ret_name = p->name;
338 	}
339 	return 0;
340 }
341 
342 /*
343  * Iterate through the section, returning the subsections which match
344  * the given name.  If name is NULL, then interate through all the
345  * subsections in the section.  The first time this routine is called,
346  * the state pointer must be null.  When this profile_find_node_subsection()
347  * returns, if the state pointer is non-NULL, then this routine should
348  * be called again.
349  *
350  * This is (plus accessor functions for the name and value given a
351  * profile node) makes this function mostly syntactic sugar for
352  * profile_find_node.
353  */
profile_find_node_subsection(struct profile_node * section,const char * name,void ** state,char ** ret_name,struct profile_node ** subsection)354 errcode_t profile_find_node_subsection(struct profile_node *section,
355 				       const char *name, void **state,
356 				       char **ret_name,
357 				       struct profile_node **subsection)
358 {
359 	struct profile_node *p;
360 	errcode_t	retval;
361 
362 	/* Solaris Kerberos */
363 	if (section == (struct profile_node *)NULL)
364 		return (PROF_NO_PROFILE);
365 
366 	retval = profile_find_node(section, name, 0, 1, state, &p);
367 	if (retval)
368 		return retval;
369 
370 	if (p) {
371 		if (subsection)
372 			*subsection = p;
373 		if (ret_name)
374 			*ret_name = p->name;
375 	}
376 	return 0;
377 }
378 
379 /*
380  * This function returns the parent of a particular node.
381  */
profile_get_node_parent(struct profile_node * section,struct profile_node ** parent)382 errcode_t profile_get_node_parent(struct profile_node *section,
383 				  struct profile_node **parent)
384 {
385 	*parent = section->parent;
386 	return 0;
387 }
388 
389 /*
390  * This is a general-purpose iterator for returning all nodes that
391  * match the specified name array.
392  */
393 struct profile_iterator {
394 	prf_magic_t		magic;
395 	profile_t		profile;
396 	int			flags;
397 	const char 		*const *names;
398 	const char		*name;
399 	prf_file_t		file;
400 	int			file_serial;
401 	int			done_idx;
402 	struct profile_node 	*node;
403 	int			num;
404 };
405 
profile_node_iterator_create(profile_t profile,const char * const * names,int flags,void ** ret_iter)406 errcode_t profile_node_iterator_create(profile_t profile,
407 				       const char *const *names, int flags,
408 				       void **ret_iter)
409 {
410 	struct profile_iterator *iter;
411 	int	done_idx = 0;
412 
413 	if (profile == 0)
414 		return PROF_NO_PROFILE;
415 	if (profile->magic != PROF_MAGIC_PROFILE)
416 		return PROF_MAGIC_PROFILE;
417 	if (!names)
418 		return PROF_BAD_NAMESET;
419 	if (!(flags & PROFILE_ITER_LIST_SECTION)) {
420 		if (!names[0])
421 			return PROF_BAD_NAMESET;
422 		done_idx = 1;
423 	}
424 
425 	if ((iter = malloc(sizeof(struct profile_iterator))) == NULL)
426 		return ENOMEM;
427 
428 	iter->magic = PROF_MAGIC_ITERATOR;
429 	iter->profile = profile;
430 	iter->names = names;
431 	iter->flags = flags;
432 	iter->file = profile->first_file;
433 	iter->done_idx = done_idx;
434 	iter->node = 0;
435 	iter->num = 0;
436 	*ret_iter = iter;
437 	return 0;
438 }
439 
profile_node_iterator_free(void ** iter_p)440 void profile_node_iterator_free(void **iter_p)
441 {
442 	struct profile_iterator *iter;
443 
444 	if (!iter_p)
445 		return;
446 	iter = *iter_p;
447 	if (!iter || iter->magic != PROF_MAGIC_ITERATOR)
448 		return;
449 	free(iter);
450 	*iter_p = 0;
451 }
452 
453 /*
454  * Note: the returned character strings in ret_name and ret_value
455  * points to the stored character string in the parse string.  Before
456  * this string value is returned to a calling application
457  * (profile_node_iterator is not an exported interface), it should be
458  * strdup()'ed.
459  */
profile_node_iterator(void ** iter_p,struct profile_node ** ret_node,char ** ret_name,char ** ret_value)460 errcode_t profile_node_iterator(void **iter_p, struct profile_node **ret_node,
461 				char **ret_name, char **ret_value)
462 {
463 	struct profile_iterator 	*iter = *iter_p;
464 	struct profile_node 		*section, *p;
465 	const char			*const *cpp;
466 	errcode_t			retval;
467 	int				skip_num = 0;
468 
469 	if (!iter || iter->magic != PROF_MAGIC_ITERATOR)
470 		return PROF_MAGIC_ITERATOR;
471 	if (iter->file && iter->file->magic != PROF_MAGIC_FILE)
472 	    return PROF_MAGIC_FILE;
473 	if (iter->file && iter->file->data->magic != PROF_MAGIC_FILE_DATA)
474 	    return PROF_MAGIC_FILE_DATA;
475 	/*
476 	 * If the file has changed, then the node pointer is invalid,
477 	 * so we'll have search the file again looking for it.
478 	 */
479 	if (iter->file) {
480 	    retval = k5_mutex_lock(&iter->file->data->lock);
481 	    if (retval)
482 		return retval;
483 	}
484 	if (iter->node && (iter->file->data->upd_serial != iter->file_serial)) {
485 		iter->flags &= ~PROFILE_ITER_FINAL_SEEN;
486 		skip_num = iter->num;
487 		iter->node = 0;
488 	}
489 	if (iter->node && iter->node->magic != PROF_MAGIC_NODE) {
490 	    if (iter->file)
491 		k5_mutex_unlock(&iter->file->data->lock);
492 	    return PROF_MAGIC_NODE;
493 	}
494 get_new_file:
495 	if (iter->node == 0) {
496 		if (iter->file == 0 ||
497 		    (iter->flags & PROFILE_ITER_FINAL_SEEN)) {
498 			if (iter->file)
499 			    k5_mutex_unlock(&iter->file->data->lock);
500 			profile_node_iterator_free(iter_p);
501 			if (ret_node)
502 				*ret_node = 0;
503 			if (ret_name)
504 				*ret_name = 0;
505 			if (ret_value)
506 				*ret_value =0;
507 			return 0;
508 		}
509 		k5_mutex_unlock(&iter->file->data->lock);
510 		if ((retval = profile_update_file(iter->file))) {
511 		    if (retval == ENOENT || retval == EACCES) {
512 			/* XXX memory leak? */
513 			iter->file = iter->file->next;
514 			if (iter->file) {
515 			    retval = k5_mutex_lock(&iter->file->data->lock);
516 			    if (retval) {
517 				profile_node_iterator_free(iter_p);
518 				return retval;
519 			    }
520 			}
521 			skip_num = 0;
522 			retval = 0;
523 			goto get_new_file;
524 		    } else {
525 			profile_node_iterator_free(iter_p);
526 			return retval;
527 		    }
528 		}
529 		retval = k5_mutex_lock(&iter->file->data->lock);
530 		if (retval) {
531 		    profile_node_iterator_free(iter_p);
532 		    return retval;
533 		}
534 		iter->file_serial = iter->file->data->upd_serial;
535 		/*
536 		 * Find the section to list if we are a LIST_SECTION,
537 		 * or find the containing section if not.
538 		 */
539 		section = iter->file->data->root;
540 		assert(section != NULL);
541 		for (cpp = iter->names; cpp[iter->done_idx]; cpp++) {
542 			for (p=section->first_child; p; p = p->next) {
543 				if (!strcmp(p->name, *cpp) && !p->value)
544 					break;
545 			}
546 			if (!p) {
547 				section = 0;
548 				break;
549 			}
550 			section = p;
551 			if (p->final)
552 				iter->flags |= PROFILE_ITER_FINAL_SEEN;
553 		}
554 		if (!section) {
555 			k5_mutex_unlock(&iter->file->data->lock);
556 			iter->file = iter->file->next;
557 			if (iter->file) {
558 			    retval = k5_mutex_lock(&iter->file->data->lock);
559 			    if (retval) {
560 				profile_node_iterator_free(iter_p);
561 				return retval;
562 			    }
563 			}
564 			skip_num = 0;
565 			goto get_new_file;
566 		}
567 		iter->name = *cpp;
568 		iter->node = section->first_child;
569 	}
570 	/*
571 	 * OK, now we know iter->node is set up correctly.  Let's do
572 	 * the search.
573 	 */
574 	for (p = iter->node; p; p = p->next) {
575 		if (iter->name && strcmp(p->name, iter->name))
576 			continue;
577 		if ((iter->flags & PROFILE_ITER_SECTIONS_ONLY) &&
578 		    p->value)
579 			continue;
580 		if ((iter->flags & PROFILE_ITER_RELATIONS_ONLY) &&
581 		    !p->value)
582 			continue;
583 		if (skip_num > 0) {
584 			skip_num--;
585 			continue;
586 		}
587 		if (p->deleted)
588 			continue;
589 		break;
590 	}
591 	iter->num++;
592 	if (!p) {
593 		k5_mutex_unlock(&iter->file->data->lock);
594 		iter->file = iter->file->next;
595 		if (iter->file) {
596 		    retval = k5_mutex_lock(&iter->file->data->lock);
597 		    if (retval) {
598 			profile_node_iterator_free(iter_p);
599 			return retval;
600 		    }
601 		}
602 		iter->node = 0;
603 		skip_num = 0;
604 		goto get_new_file;
605 	}
606 	k5_mutex_unlock(&iter->file->data->lock);
607 	if ((iter->node = p->next) == NULL)
608 		iter->file = iter->file->next;
609 	if (ret_node)
610 		*ret_node = p;
611 	if (ret_name)
612 		*ret_name = p->name;
613 	if (ret_value)
614 		*ret_value = p->value;
615 	return 0;
616 }
617 
618 /*
619  * Remove a particular node.
620  *
621  * TYT, 2/25/99
622  */
profile_remove_node(struct profile_node * node)623 errcode_t profile_remove_node(struct profile_node *node)
624 {
625 	CHECK_MAGIC(node);
626 
627 	if (node->parent == 0)
628 		return PROF_EINVAL; /* Can't remove the root! */
629 
630 	node->deleted = 1;
631 
632 	return 0;
633 }
634 
635 /*
636  * Set the value of a specific node containing a relation.
637  *
638  * TYT, 2/25/99
639  */
profile_set_relation_value(struct profile_node * node,const char * new_value)640 errcode_t profile_set_relation_value(struct profile_node *node,
641 				     const char *new_value)
642 {
643 	char	*cp;
644 
645 	CHECK_MAGIC(node);
646 
647 	if (!node->value)
648 		return PROF_SET_SECTION_VALUE;
649 
650 	cp = malloc(strlen(new_value)+1);
651 	if (!cp)
652 		return ENOMEM;
653 
654 	strcpy(cp, new_value);
655 	free(node->value);
656 	node->value = cp;
657 
658 	return 0;
659 }
660 
661 /*
662  * Rename a specific node
663  *
664  * TYT 2/25/99
665  */
profile_rename_node(struct profile_node * node,const char * new_name)666 errcode_t profile_rename_node(struct profile_node *node, const char *new_name)
667 {
668 	char			*new_string;
669 	struct profile_node 	*p, *last;
670 
671 	CHECK_MAGIC(node);
672 
673 	if (strcmp(new_name, node->name) == 0)
674 		return 0;	/* It's the same name, return */
675 
676 	/*
677 	 * Make sure we can allocate memory for the new name, first!
678 	 */
679 	new_string = malloc(strlen(new_name)+1);
680 	if (!new_string)
681 		return ENOMEM;
682 	strcpy(new_string, new_name);
683 
684 	/*
685 	 * Find the place to where the new node should go.  We look
686 	 * for the place *after* the last match of the node name,
687 	 * since order matters.
688 	 */
689 	for (p=node->parent->first_child, last = 0; p; last = p, p = p->next) {
690 		if (strcmp(p->name, new_name) > 0)
691 			break;
692 	}
693 
694 	/*
695 	 * If we need to move the node, do it now.
696 	 */
697 	if ((p != node) && (last != node)) {
698 		/*
699 		 * OK, let's detach the node
700 		 */
701 		if (node->prev)
702 			node->prev->next = node->next;
703 		else
704 			node->parent->first_child = node->next;
705 		if (node->next)
706 			node->next->prev = node->prev;
707 
708 		/*
709 		 * Now let's reattach it in the right place.
710 		 */
711 		if (p)
712 			p->prev = node;
713 		if (last)
714 			last->next = node;
715 		else
716 			node->parent->first_child = node;
717 		node->next = p;
718 		node->prev = last;
719 	}
720 
721 	free(node->name);
722 	node->name = new_string;
723 	return 0;
724 }
725