3 * $Id: class.c,v 1.8 1998/06/08 11:20:36 mdw Exp $
5 * Handling classes of things nicely
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of `become'
14 * `Become' is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (at your option) any later version.
19 * `Become' is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
24 * You should have received a copy of the GNU General Public License
25 * along with `become'; if not, write to the Free Software Foundation,
26 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
29 /*----- Revision history --------------------------------------------------*
32 * Revision 1.8 1998/06/08 11:20:36 mdw
33 * (class__wildMatch) Fixed bug which overran pattern string, spotted by
36 * Revision 1.7 1998/01/12 16:45:50 mdw
39 * Revision 1.6 1997/09/17 10:14:56 mdw
40 * Complete rewrite to support class trees. Makes the behaviour of the set
41 * operators much more logical.
43 * Revision 1.5 1997/08/20 16:16:13 mdw
44 * Patch memory leak. Don't try to trace when tracing's turned off.
46 * Revision 1.4 1997/08/07 09:56:37 mdw
47 * (Log entry for previous version is bogus.) Minor changes to host
50 * Revision 1.2 1997/08/04 10:24:21 mdw
51 * Sources placed under CVS control.
53 * Revision 1.1 1997/07/21 13:47:52 mdw
58 /*----- Header files ------------------------------------------------------*/
60 /* --- ANSI headers --- */
66 /* --- Unix headers --- */
68 #include <sys/types.h>
69 #include <sys/socket.h>
71 #include <netinet/in.h>
73 #include <arpa/inet.h>
77 /* --- Local headers --- */
84 /*----- Global variables --------------------------------------------------*/
86 static class_node class__all
= { clType_all
| clNode_any
, -1, { 0 }};
87 class_node
*class_all
= &class__all
;
89 static class_node class__none
= { clType_all
| clNode_any
, -1, { 0 }};
90 class_node
*class_none
= &class__none
;
92 /*----- Wildcard matching -------------------------------------------------*/
94 /* --- @class__wildMatch@ --- *
96 * Arguments: @const char *pat@ = pointer to pattern string
97 * @const char *p@ = pointer to target string
99 * Returns: Zero if no match, nonzero if match.
101 * Use: Wildcard-matches the pattern against the target string.
104 static int class__wildMatch(const char *pat
, const char *p
)
107 if (*pat
== 0 && *p
== 0)
108 return (42); /* For sadism's sake */
109 else if (*pat
== '*') {
115 if (class__wildMatch(pat
, p
))
116 return (27); /* Nyahaha */
120 } else if (*pat
== '?' || *pat
== *p
)
127 /*----- Creating new class nodes ------------------------------------------*/
129 /* --- @class_fromString@ --- *
131 * Arguments: @unsigned type@ = a type field
132 * @const char *s@ = pointer to string to copy
134 * Returns: A pointer to a class node containing that string, typed to
135 * be the right thing.
137 * Use: Given a string, wrap a class node around it. The node has
138 * one reference (the one you get returned). The string is
139 * copied, so you can get rid of your original one if you like.
142 class_node
*class_fromString(unsigned type
, const char *s
)
144 class_node
*c
= xmalloc(sizeof(*c
));
145 c
->type
= type
| clNode_immed
;
146 if (s
[strcspn(s
, "*?")] == 0)
147 c
->type
|= clFlag_friendly
;
153 /* --- @class_fromUser@ --- *
155 * Arguments: @unsigned type@ = a type field
156 * @uid_t u@ = a user-id number
158 * Returns: A pointer to a class node containing the uid, typed to be
159 * the thing you asked for. Hopefully this will be
162 * Use: Given a uid, wrap a class node around it.
165 class_node
*class_fromUser(unsigned type
, uid_t u
)
167 class_node
*c
= xmalloc(sizeof(*c
));
168 c
->type
= type
| clNode_immed
| clFlag_friendly
;
174 /*----- Reference counter tricks ------------------------------------------*/
176 /* --- @class_inc@ --- *
178 * Arguments: @class_node *c@ = pointer to a class block
182 * Use: Adds a reference to the class definition.
185 void class_inc(class_node
*c
)
187 if (c
!= class_all
&& c
!= class_none
)
191 /* --- @class_dec@ --- *
193 * Arguments: @class_node *c@ = pointer to a class block
197 * Use: Removes a reference to a class block.
200 void class_dec(class_node
*c
)
204 for (cc
= 0; c
; c
= cc
, cc
= 0) {
205 if (c
== class_all
|| c
== class_none
|| --c
->ref
)
207 switch (c
->type
& clNode_mask
) {
212 if (c
->type
& (clType_host
| clType_command
))
216 sym_destroyTable(&c
->v
.t
);
229 /* --- @class_mod@ --- *
231 * Arguments: @class_node *c@ = pointer to a class node
233 * Returns: A pointer to a class node, maybe the same one, maybe not,
234 * with a reference count of 1, containing the same data.
236 * Use: Gives you a node which you can modify. Don't call this
237 * for @class_all@ or @class_none@.
240 class_node
*class_mod(class_node
*c
)
247 cc
= xmalloc(sizeof(*cc
));
250 switch (c
->type
& clNode_mask
) {
252 die("internal error: class_mod called on non-modifiable class node");
256 if (c
->type
& clType_user
)
259 cc
->v
.s
= xstrdup(c
->v
.s
);
266 sym_createTable(&cc
->v
.t
);
267 for (sym_createIter(&i
, &c
->v
.t
); (b
= sym_next(&i
)) != 0; )
268 sym_find(&cc
->v
.t
, b
->name
, b
->len
, sizeof(sym_base
), 0);
274 cc
->v
.c
.l
= c
->v
.c
.l
;
275 cc
->v
.c
.r
= c
->v
.c
.r
;
276 class_inc(cc
->v
.c
.l
);
277 class_inc(cc
->v
.c
.r
);
285 /*----- Some weirder operations on classes --------------------------------*/
287 /* --- @class__hashify@ --- *
289 * Arguments: @class_node *c@ = pointer to a node
291 * Returns: A pointer to a hash node containing the node's value.
293 * Use: The original node must have type `immediate', and it must
294 * be friendly. The old reference is discarded -- you get this
298 static class_node
*class__hashify(class_node
*c
)
300 /* --- Some sanity checking --- */
302 if (~c
->type
& clFlag_friendly
)
303 die("internal error: class__hashify can't hashify unfriendly nodes");
304 if ((c
->type
& clNode_mask
) != clNode_immed
)
305 die("internal error: class__hashify can't hashify non-immediate nodes");
307 /* --- Split off a private copy of the node --- */
311 c
->type
= (c
->type
& clType_mask
) | clNode_hash
| clFlag_friendly
;
313 if (c
->type
& clType_user
) {
315 sym_createTable(&c
->v
.t
);
316 sym_find(&c
->v
.t
, (char *)&u
, sizeof(u
), sizeof(sym_base
), 0);
319 sym_createTable(&c
->v
.t
);
320 sym_find(&c
->v
.t
, s
, -1, sizeof(sym_base
), 0);
327 /*----- Arithmetic on classes ---------------------------------------------*/
329 /* --- @class__binop@ --- *
331 * Arguments: @class_node *l@ = left argument
332 * @class_node *r@ = right argument
333 * @unsigned op@ = the binop code
335 * Returns: A class node representing the result of a binary operation
338 * Use: Performs a binary operation on classes. If the types don't
339 * match, then a null pointer is returned. Both @l@ and @r@
340 * may be modified, and will be decremented before they get
341 * returned to you. If you don't want that to happen, ensure
342 * that you've claimed a reference to the original versions.
344 * If both nodes are `friendly' (see below), then an attempt is
345 * made to combine them sensibly using a hashtable.
347 * If one or both nodes is/are unfriendly, a binop node is
348 * created with type @op@ to allow the matcher to decide on
349 * membership appropriately at match time.
351 * A friendly node is one which can be placed in a hash table to
352 * speed up searching. It's friendly, because it doesn't mind
353 * living with other nodes. Uid numbers are friendly.
354 * Wildcarded strings aren't. Hashtables are trivially
358 class_node
*class__binop(class_node
*l
, class_node
*r
, int op
)
360 unsigned type
= l
->type
& r
->type
& clType_mask
;
361 unsigned lnode
= l
->type
& clNode_mask
, rnode
= r
->type
& clNode_mask
;
363 /* --- Check for compatible types --- */
371 /* --- Handle `friendly' nodes --- */
373 if ((l
->type
& r
->type
& clFlag_friendly
)) {
375 /* --- Consider promoting an item to a hash --- *
377 * If both are immediate nodes, and they're both `friendly', we can
378 * profitably hash them together.
380 * Life gets complicated when we do subtraction, because it's not
381 * commutative. In this case, I have to promote the left operand anyway.
384 if (lnode
== clNode_immed
&&
385 (rnode
== clNode_immed
|| op
== clNode_diff
)) {
387 /* --- Quick check for triviality --- *
389 * There are some more short-cuts I can employ if the values are
393 if (rnode
== clNode_immed
) {
395 /* --- See whether the two items are equal --- */
397 int eq
= (type
& clType_user ?
398 l
->v
.u
== r
->v
.u
: strcmp(l
->v
.s
, r
->v
.s
) == 0);
400 /* --- Now do something appropriate --- */
429 /* --- Turn @l@ into a hash containing itself --- */
431 l
= class__hashify(l
);
435 /* --- Otherwise, make @l@ the hash --- *
437 * Both @l@ and @r@ are friendly. Since they're not both immediates,
438 * one must be a hash.
441 else if ((l
->type
& clNode_mask
) == clNode_immed
) {
445 tn
= l
, l
= r
, r
= tn
;
446 tt
= lnode
, lnode
= rnode
, rnode
= tt
;
449 /* --- Now merge @r@ with @l@ --- */
455 /* --- The union operation isn't hard --- */
458 if (rnode
== clNode_immed
) {
459 if (type
& clType_user
) {
460 sym_find(&l
->v
.t
, (char *)&r
->v
.u
,
461 sizeof(r
->v
.u
), sizeof(sym_base
), 0);
463 sym_find(&l
->v
.t
, r
->v
.s
, -1, sizeof(sym_base
), 0);
468 for (sym_createIter(&i
, &r
->v
.t
); (b
= sym_next(&i
)) != 0; )
469 sym_find(&l
->v
.t
, b
->name
, b
->len
, sizeof(sym_base
), 0);
473 /* --- Set difference is similar in spirit --- */
476 if (rnode
== clNode_immed
) {
479 if (type
& clType_user
)
480 f
= sym_find(&l
->v
.t
, (char *)&r
->v
.u
, sizeof(r
->v
.u
), 0, 0);
482 f
= sym_find(&l
->v
.t
, r
->v
.s
, -1, 0, 0);
484 sym_remove(&l
->v
.t
, f
);
489 for (sym_createIter(&i
, &r
->v
.t
); (b
= sym_next(&i
)) != 0; ) {
490 if ((f
= sym_find(&l
->v
.t
, b
->name
, b
->len
, 0, 0)) != 0)
491 sym_remove(&l
->v
.t
, f
);
496 /* --- Intersection is wild and wacky --- */
499 if (rnode
== clNode_immed
) {
502 if (type
& clType_user
)
503 f
= sym_find(&l
->v
.t
, (char *)&r
->v
.u
, sizeof(r
->v
.u
), 0, 0);
505 f
= sym_find(&l
->v
.t
, r
->v
.s
, -1, 0, 0);
518 for (sym_createIter(&i
, &l
->v
.t
); (b
= sym_next(&i
)) != 0; ) {
519 if (!sym_find(&r
->v
.t
, b
->name
, b
->len
, 0, 0))
520 sym_remove(&l
->v
.t
, b
);
526 /* --- Now trim the @l@ table to size --- *
528 * It may have lost a load of elements. Maybe it can be represented
529 * better as an immediate or even as @class_none@.
538 sym_createIter(&i
, &l
->v
.t
);
539 if ((b
= sym_next(&i
)) == 0) {
544 if (type
& clType_user
) {
545 uid_t u
= *(uid_t
*)b
->name
;
546 sym_destroyTable(&l
->v
.t
);
547 l
->type
= (l
->type
& ~clNode_mask
) | clNode_immed
;
550 char *s
= xstrdup(b
->name
);
551 sym_destroyTable(&l
->v
.t
);
552 l
->type
= (l
->type
& ~clNode_mask
) | clNode_immed
;
563 /* --- Unfriendly nodes --- *
565 * Create a binop node and return that. If @l@ is a binop node, and @r@
566 * isn't, and the operation isn't set difference (i.e., it's commutative)
567 * then swap the two over to lessen the depth of recursion later.
571 class_node
*c
= xmalloc(sizeof(*c
));
575 if (lnode
>= clNode_binop
&& rnode
< clNode_binop
&& op
!= clNode_diff
) {
586 /* --- @class_union@ --- *
588 * Arguments: @class_node *l@ = left argument
589 * @class_node *r@ = right argument
591 * Returns: A class node representing the union of the two classes.
593 * Use: Performs the union operation on classes. If the types don't
594 * match, then a null pointer is returned. Both @l@ and @r@
595 * may be modified, and will be decremented before they get
596 * returned to you. If you don't want that to happen, ensure
597 * that you've claimed a reference to the original versions.
600 class_node
*class_union(class_node
*l
, class_node
*r
)
602 /* --- Check for the really simple cases --- */
604 if (l
== class_all
|| r
== class_all
) {
615 /* --- Do the job --- */
617 return (class__binop(l
, r
, clNode_union
));
620 /* --- @class_diff@ --- *
622 * Arguments: @class_node *l@ = left argument
623 * @class_node *r@ = right argument
625 * Returns: A class node representing the difference of the two classes.
627 * Use: Performs the set difference operation on classes. If the
628 * types don't match, then a null pointer is returned. Both
629 * @l@ and @r@ may be modified, and will be decremented before
630 * they get returned to you. If you don't want that to happen,
631 * ensure that you've claimed a reference to the original
635 class_node
*class_diff(class_node
*l
, class_node
*r
)
637 /* --- Check for the really simple cases --- */
639 if (l
== class_none
|| r
== class_all
) {
648 /* --- Do the job --- */
650 return (class__binop(l
, r
, clNode_diff
));
653 /* --- @class_isect@ --- *
655 * Arguments: @class_node *l@ = left argument
656 * @class_node *r@ = right argument
658 * Returns: A class node representing the intersection of the two
661 * Use: Performs the intersecion operation on classes. If the types
662 * don't match, then a null pointer is returned. Both @l@ and
663 * @r@ may be modified, and will be decremented before they get
664 * returned to you. If you don't want that to happen, ensure
665 * that you've claimed a reference to the original versions.
668 class_node
*class_isect(class_node
*l
, class_node
*r
)
670 /* --- Check for the really simple cases --- */
672 if (l
== class_none
|| r
== class_none
) {
683 /* --- Do the job --- */
685 return (class__binop(l
, r
, clNode_isect
));
688 /*----- Building the predefined classes -----------------------------------*/
690 /* --- @class_addUser@ --- *
692 * Arguments: @class_node *c@ = pointer to a class node (may be null)
693 * @uid_t u@ = user id number
695 * Returns: Pointer to the combined node.
697 * Use: Adds a user to a node, maybe hashifying it.
700 class_node
*class_addUser(class_node
*c
, uid_t u
)
703 return (class_fromUser(clType_user
, u
));
704 if ((c
->type
& clNode_mask
) == clNode_immed
)
705 c
= class__hashify(c
);
706 sym_find(&c
->v
.t
, (char *)&u
, sizeof(u
), sizeof(sym_base
), 0);
710 /* --- @class_addString@ --- *
712 * Arguments: @class_node *c@ = pointer to a class node (may be null)
713 * @const char *s@ = pointer to a string
715 * Returns: Pointer to the combined node.
717 * Use: Adds a user to a node, maybe hashifying it.
720 class_node
*class_addString(class_node
*c
, const char *s
)
722 class_node
*n
= class_fromString(clType_host
, s
); /* hack */
724 return (class_union(c
, n
));
729 /*----- Matching functions ------------------------------------------------*/
731 /* --- @class_matchUser@ --- *
733 * Arguments: @class_node *c@ = pointer to root class node
734 * @uid_t u@ = user id number
736 * Returns: Nonzero if it matches, zero if it doesn't.
738 * Use: Determines whether a user is matched by a class. Assumes
739 * that the types are correct.
742 int class_matchUser(class_node
*c
, uid_t u
)
746 for (cc
= 0; c
; c
= cc
, cc
= 0) {
751 switch (c
->type
& clNode_mask
) {
753 return (u
== c
->v
.u
);
756 return (sym_find(&c
->v
.t
, (char *)&u
, sizeof(u
), 0, 0) != 0);
759 if (class_matchUser(c
->v
.c
.l
, u
))
764 if (!class_matchUser(c
->v
.c
.l
, u
))
769 return (class_matchUser(c
->v
.c
.l
, u
) &&
770 !class_matchUser(c
->v
.c
.r
, u
));
775 die("internal error: can't get here in class_matchUser");
779 /* --- @class_matchCommand@ --- *
781 * Arguments: @class_node *c@ = pointer to root class node
782 * @const char *s@ = pointer to a string
784 * Returns: Nonzero if it matches, zero if it doesn't.
786 * Use: Determines whether a string is matched by a class. Assumes
787 * that the types are correct.
790 int class_matchCommand(class_node
*c
, const char *s
)
794 for (cc
= 0; c
; c
= cc
, cc
= 0) {
799 switch (c
->type
& clNode_mask
) {
801 return (class__wildMatch(c
->v
.s
, s
));
804 return (sym_find(&c
->v
.t
, s
, -1, 0, 0) != 0);
807 if (class_matchCommand(c
->v
.c
.l
, s
))
812 if (!class_matchCommand(c
->v
.c
.l
, s
))
817 return (class_matchCommand(c
->v
.c
.l
, s
) &&
818 !class_matchCommand(c
->v
.c
.r
, s
));
823 die("internal error: can't get here in class_matchCommand");
827 /* --- @class_matchHost@ --- *
829 * Arguments: @class_node *c@ = pointer to root class node
830 * @struct in_addr a@ = IP address to match
832 * Returns: Nonzero if it matches, zero if it doesn't.
834 * Use: Determines whether a host matches a host class. Assumes
835 * that the types are correct. The actual mechanism is a bit
836 * odd here, but I think this is the Right Thing. At each stage
837 * I try to match %%@/all/%% of the possible names for the host.
838 * Thus host `splat' with address 1.2.3.4 would fail to match
839 * the class "1.2.*" - "splat". This seems to be what the
840 * author intuitively expects. It's just a bit weird.
843 static int class__doMatchHost(class_node
*c
, const char *ip
,
844 const char *name
, char **aliases
)
848 for (cc
= 0; c
; c
= cc
, cc
= 0) {
853 switch (c
->type
& clNode_mask
) {
855 if ((ip
&& class__wildMatch(c
->v
.s
, ip
)) ||
856 (name
&& class__wildMatch(c
->v
.s
, name
)))
858 if (aliases
) for (; *aliases
; aliases
++) {
859 if (class__wildMatch(c
->v
.s
, *aliases
))
865 if ((ip
&& sym_find(&c
->v
.t
, ip
, -1, 0, 0)) ||
866 (name
&& sym_find(&c
->v
.t
, name
, -1, 0, 0)))
868 if (aliases
) for (; *aliases
; aliases
++) {
869 if (sym_find(&c
->v
.t
, *aliases
, -1, 0, 0))
875 if (class__doMatchHost(c
->v
.c
.l
, ip
, name
, aliases
))
880 if (!class__doMatchHost(c
->v
.c
.l
, ip
, name
, aliases
))
885 return (class__doMatchHost(c
->v
.c
.l
, ip
, name
, aliases
) &&
886 !class__doMatchHost(c
->v
.c
.r
, ip
, name
, aliases
));
891 die("internal error: can't get here in class_matchUser");
895 int class_matchHost(class_node
*c
, struct in_addr a
)
897 char *ip
, *name
, **aliases
;
901 if ((h
= gethostbyaddr((char *)&a
, sizeof(a
), AF_INET
)) != 0) {
903 aliases
= h
->h_aliases
;
909 return (class__doMatchHost(c
, ip
, name
, aliases
));
912 /*----- Debugging code ----------------------------------------------------*/
914 /* --- @class_dump@ --- *
916 * Argumemnts: @class_node *c@ = pointer to root node
917 * @int indent@ = indent depth
921 * Use: Dumps a class to the trace output.
924 void class_dump(class_node
*c
, int indent
)
928 static char *types
[] = {
936 static char *nodes
[] = {
943 "binop: intersection"
946 /* --- Handle some magical cases --- */
948 if (c
== class_all
) {
949 trace(TRACE_RULE
, "rule:%*s class ALL", indent
* 2, "");
952 if (c
== class_none
) {
953 trace(TRACE_RULE
, "rule:%*s class NONE", indent
* 2, "");
957 /* --- Dump basic type information --- */
959 trace(TRACE_RULE
, "rule:%*s type == [%s], node type == [%s]%s",
961 types
[c
->type
& clType_mask
],
962 nodes
[(c
->type
& clNode_mask
) >> 4],
963 (c
->type
& clFlag_friendly
) ?
" Friendly" : "");
965 /* --- Now trace the contents --- */
967 switch (c
->type
& clNode_mask
) {
969 if (c
->type
& clType_user
) {
970 trace(TRACE_RULE
, "rule:%*s user %lu",
971 indent
* 2, "", (unsigned long)c
->v
.u
);
973 trace(TRACE_RULE
, "rule:%*s `%s'", indent
* 2, "", c
->v
.s
);
979 for (sym_createIter(&i
, &c
->v
.t
); (b
= sym_next(&i
)) != 0; ) {
980 if (c
->type
& clType_user
) {
981 trace(TRACE_RULE
, "rule:%*s user %lu",
982 indent
* 2, "", (unsigned long)*(uid_t
*)b
->name
);
984 trace(TRACE_RULE
, "rule:%*s `%s'", indent
* 2, "", b
->name
);
990 class_dump(c
->v
.c
.l
, indent
+ 1);
991 class_dump(c
->v
.c
.r
, indent
+ 1);
998 /*----- That's all, folks -------------------------------------------------*/