From 50a87c1f8ddb1abd3b80bbc99d99f7806cc40374 Mon Sep 17 00:00:00 2001 From: mdw Date: Wed, 17 Sep 1997 10:14:56 +0000 Subject: [PATCH] Complete rewrite to support class trees. Makes the behaviour of the set operators much more logical. --- src/class.c | 917 +++++++++++++++++++++++++++++++++++++++++++++++++++--------- src/class.h | 240 ++++++++++++---- 2 files changed, 974 insertions(+), 183 deletions(-) diff --git a/src/class.c b/src/class.c index 990822d..49b1341 100644 --- a/src/class.c +++ b/src/class.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: class.c,v 1.5 1997/08/20 16:16:13 mdw Exp $ + * $Id: class.c,v 1.6 1997/09/17 10:14:56 mdw Exp $ * * Handling classes of things nicely * @@ -29,7 +29,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: class.c,v $ - * Revision 1.5 1997/08/20 16:16:13 mdw + * Revision 1.6 1997/09/17 10:14:56 mdw + * Complete rewrite to support class trees. Makes the behaviour of the set + * operators much more logical. + * + * Revision 1.5 1997/08/20 16:16:13 mdw * Patch memory leak. Don't try to trace when tracing's turned off. * * Revision 1.4 1997/08/07 09:56:37 mdw @@ -67,14 +71,16 @@ #include "become.h" #include "class.h" -#include "set.h" #include "sym.h" #include "utils.h" /*----- Global variables --------------------------------------------------*/ -static classdef class__all = { clType_all, -1, 0 }; -classdef *class_all = &class__all; +static class_node class__all = { clType_all | clNode_any, -1, { 0 }}; +class_node *class_all = &class__all; + +static class_node class__none = { clType_all | clNode_any, -1, { 0 }}; +class_node *class_none = &class__none; /*----- Wildcard matching -------------------------------------------------*/ @@ -101,7 +107,7 @@ static int class__wildMatch(const char *pat, const char *p) return (27); /* Nyahaha */ p++; } while (*p); - return (0); + return (pat[1] == 0); } else if (*pat == '?' || *pat == *p) p++, pat++; else @@ -109,235 +115,874 @@ static int class__wildMatch(const char *pat, const char *p) } } -/*----- Main code ---------------------------------------------------------*/ +/*----- Creating new class nodes ------------------------------------------*/ + +/* --- @class_fromString@ --- * + * + * Arguments: @unsigned type@ = a type field + * @const char *s@ = pointer to string to copy + * + * Returns: A pointer to a class node containing that string, typed to + * be the right thing. + * + * Use: Given a string, wrap a class node around it. The node has + * one reference (the one you get returned). The string is + * copied, so you can get rid of your original one if you like. + */ + +class_node *class_fromString(unsigned type, const char *s) +{ + class_node *c = xmalloc(sizeof(*c)); + c->type = type | clNode_immed; + if (s[strcspn(s, "*?")] == 0) + c->type |= clFlag_friendly; + c->ref = 1; + c->v.s = xstrdup(s); + return (c); +} -/* --- @class_create@ --- * +/* --- @class_fromUser@ --- * * - * Arguments: @unsigned type@ = type of the class to create - * @sym_table *t@ = pointer to symbol table which stores info + * Arguments: @unsigned type@ = a type field + * @uid_t u@ = a user-id number * - * Returns: Pointer to a @classdef@ which maintains the class's info. + * Returns: A pointer to a class node containing the uid, typed to be + * the thing you asked for. Hopefully this will be + * @clType_user@. * - * Use: Creates a new class definition. The new definition has one - * reference attached to it (which is the one you get returned). + * Use: Given a uid, wrap a class node around it. */ -classdef *class_create(unsigned type, sym_table *t) +class_node *class_fromUser(unsigned type, uid_t u) { - classdef *c = xmalloc(sizeof(*c)); - c->type = type; + class_node *c = xmalloc(sizeof(*c)); + c->type = type | clNode_immed | clFlag_friendly; c->ref = 1; - c->t = t; + c->v.u = u; return (c); } +/*----- Reference counter tricks ------------------------------------------*/ + /* --- @class_inc@ --- * * - * Arguments: @classdef *c@ = pointer to a class block + * Arguments: @class_node *c@ = pointer to a class block * * Returns: --- * * Use: Adds a reference to the class definition. */ -void class_inc(classdef *c) +void class_inc(class_node *c) { - if (c != class_all) + if (c != class_all && c != class_none) c->ref++; } /* --- @class_dec@ --- * * - * Arguments: @classdef *c@ = pointer to a class block + * Arguments: @class_node *c@ = pointer to a class block * * Returns: --- * * Use: Removes a reference to a class block. */ -void class_dec(classdef *c) +void class_dec(class_node *c) { - if (c != class_all && !--c->ref) { - sym_destroyTable(c->t); - free(c->t); + class_node *cc; + + for (cc = 0; c; c = cc, cc = 0) { + if (c == class_all || c == class_none || --c->ref) + continue; + switch (c->type & clNode_mask) { + case clNode_any: + /* Nothing to do */ + break; + case clNode_immed: + if (c->type & (clType_host | clType_command)) + free(c->v.s); + break; + case clNode_hash: + sym_destroyTable(&c->v.t); + break; + case clNode_union: + case clNode_diff: + case clNode_isect: + class_dec(c->v.c.l); + cc = c->v.c.r; + break; + } free(c); } } -/* --- @class_userMatch@ --- * +/* --- @class_mod@ --- * * - * Arguments: @classdef *c@ = pointer to a class block - * @int u@ = uid number to check against + * Arguments: @class_node *c@ = pointer to a class node * - * Returns: Zero if no match, nonzero if it matched. + * Returns: A pointer to a class node, maybe the same one, maybe not, + * with a reference count of 1, containing the same data. * - * Use: Looks to see if a user is in a group. + * Use: Gives you a node which you can modify. Don't call this + * for @class_all@ or @class_none@. */ -int class_userMatch(classdef *c, int u) +class_node *class_mod(class_node *c) { - if (~c->type & clType_user) - return (0); - else if (c == class_all) { - T( trace(TRACE_CHECK, "check: user %i matched by all", u); ) - return (1); - } else { - sym_base *s = sym_find(c->t, (char *)&u, sizeof(u), 0, 0); - T( trace(TRACE_CHECK, - s ? "check: user %i matched" : "check: user %i not matched", - u); ) - return (s != 0); + class_node *cc; + + if (c->ref == 1) + return (c); + + cc = xmalloc(sizeof(*cc)); + cc->type = c->type; + cc->ref = 1; + switch (c->type & clNode_mask) { + case clNode_any: + die("internal error: class_mod called on non-modifiable class node"); + break; + + case clNode_immed: + if (c->type & clType_user) + cc->v.u = c->v.u; + else + cc->v.s = xstrdup(c->v.s); + break; + + case clNode_hash: { + sym_iter i; + sym_base *b; + + sym_createTable(&cc->v.t); + for (sym_createIter(&i, &c->v.t); (b = sym_next(&i)) != 0; ) + sym_find(&cc->v.t, b->name, b->len, sizeof(sym_base), 0); + } break; + + case clNode_union: + case clNode_diff: + case clNode_isect: + cc->v.c.l = c->v.c.l; + cc->v.c.r = c->v.c.r; + class_inc(cc->v.c.l); + class_inc(cc->v.c.r); + break; } + + class_dec(c); + return (cc); } -/* --- @class_commandMatch@ --- * +/*----- Some weirder operations on classes --------------------------------*/ + +/* --- @class__hashify@ --- * * - * Arguments: @classdef *c@ = pointer to a class block - * @const char *p@ = pointer to command string to match + * Arguments: @class_node *c@ = pointer to a node * - * Returns: Zero for no match, nonzero if it matched. + * Returns: A pointer to a hash node containing the node's value. * - * Use: Tries to match a string against the wildcard patterns in the - * given class. Note that this involves examining all the - * items, so it's not too quick. Then again, you don't have - * big command classes, do you...? + * Use: The original node must have type `immediate', and it must + * be friendly. The old reference is discarded -- you get this + * one instead. */ -int class_commandMatch(classdef *c, const char *p) +static class_node *class__hashify(class_node *c) { - sym_iter i; - sym_base *s; + /* --- Some sanity checking --- */ - if (~c->type & clType_command) - return (0); - else if (c == class_all) { - T( trace(TRACE_CHECK, "check: command `%s' matched by all", p); ) - return (1); + if (~c->type & clFlag_friendly) + die("internal error: class__hashify can't hashify unfriendly nodes"); + if ((c->type & clNode_mask) != clNode_immed) + die("internal error: class__hashify can't hashify non-immediate nodes"); + + /* --- Split off a private copy of the node --- */ + + c = class_mod(c); + + c->type = (c->type & clType_mask) | clNode_hash | clFlag_friendly; + + if (c->type & clType_user) { + uid_t u = c->v.u; + sym_createTable(&c->v.t); + sym_find(&c->v.t, (char *)&u, sizeof(u), sizeof(sym_base), 0); } else { - for (sym_createIter(&i, c->t); (s = sym_next(&i)) != 0; ) { - if (class__wildMatch(s->name, p)) { - T( trace(TRACE_CHECK, "check: command `%s' matched by `%s'", - p, s->name); ) - return (1); - } - } - T( trace(TRACE_CHECK, "check: command `%s' not matched", p); ) - return (0); + char *s = c->v.s; + sym_createTable(&c->v.t); + sym_find(&c->v.t, s, -1, sizeof(sym_base), 0); + free(s); } + + return (c); } -/* --- @class_hostMatch@ --- * +/*----- Arithmetic on classes ---------------------------------------------*/ + +/* --- @class__binop@ --- * + * + * Arguments: @class_node *l@ = left argument + * @class_node *r@ = right argument + * @unsigned op@ = the binop code * - * Arguments: @classdef *c@ = pointer to class block - * @struct in_addr addr@ = IP address to match + * Returns: A class node representing the result of a binary operation + * upon two classes. * - * Returns: Zero for no match, nonzero if it matched. + * Use: Performs a binary operation on classes. If the types don't + * match, then a null pointer is returned. Both @l@ and @r@ + * may be modified, and will be decremented before they get + * returned to you. If you don't want that to happen, ensure + * that you've claimed a reference to the original versions. * - * Use: Tries to match an IP address against the patterns and masks - * in the given class. + * If both nodes are `friendly' (see below), then an attempt is + * made to combine them sensibly using a hashtable. + * + * If one or both nodes is/are unfriendly, a binop node is + * created with type @op@ to allow the matcher to decide on + * membership appropriately at match time. + * + * A friendly node is one which can be placed in a hash table to + * speed up searching. It's friendly, because it doesn't mind + * living with other nodes. Uid numbers are friendly. + * Wildcarded strings aren't. Hashtables are trivially + * friendly. */ -int class_hostMatch(classdef *c, struct in_addr addr) +class_node *class__binop(class_node *l, class_node *r, int op) { - sym_iter i; - sym_base *s; - const char *a; - struct hostent *he; - char **p; + unsigned type = l->type & r->type & clType_mask; + unsigned lnode = l->type & clNode_mask, rnode = r->type & clNode_mask; + + /* --- Check for compatible types --- */ - if (~c->type & clType_host) + if (!type) { + class_dec(l); + class_dec(r); return (0); - else if (c == class_all) { - T( trace(TRACE_CHECK, "check: host %s matched by all", - inet_ntoa(addr)); ) - return (1); - } else { + } - /* --- Get the dotted-quad and other names for the address --- */ + /* --- Handle `friendly' nodes --- */ - if ((a = inet_ntoa(addr)) == 0) { - T( trace(TRACE_CHECK, "check: couldn't translate address (erk!)"); ) - return (0); + if ((l->type & r->type & clFlag_friendly)) { + + /* --- Consider promoting an item to a hash --- * + * + * If both are immediate nodes, and they're both `friendly', we can + * profitably hash them together. + * + * Life gets complicated when we do subtraction, because it's not + * commutative. In this case, I have to promote the left operand anyway. + */ + + if (lnode == clNode_immed && + (rnode == clNode_immed || op == clNode_diff)) { + + /* --- Quick check for triviality --- * + * + * There are some more short-cuts I can employ if the values are + * the same. + */ + + if (rnode == clNode_immed) { + + /* --- See whether the two items are equal --- */ + + int eq = (type & clType_user ? + l->v.u == r->v.u : strcmp(l->v.s, r->v.s) == 0); + + /* --- Now do something appropriate --- */ + + switch (op) { + case clNode_union: + if (eq) { + class_dec(r); + return (l); + } + break; + case clNode_diff: + if (eq) { + class_dec(l); + class_dec(r); + return (class_none); + } + break; + case clNode_isect: + if (eq) { + class_dec(r); + return (l); + } else { + class_dec(l); + class_dec(r); + return (class_none); + } + break; + } + } + + /* --- Turn @l@ into a hash containing itself --- */ + + l = class__hashify(l); + lnode = clNode_hash; } - if ((he = gethostbyaddr((char *)&addr, sizeof(addr), AF_INET)) == 0) - T( trace(TRACE_CHECK, "check: couldn't resolve hostname for %s", a); ) + /* --- Otherwise, make @l@ the hash --- * + * + * Both @l@ and @r@ are friendly. Since they're not both immediates, + * one must be a hash. + */ - /* --- Now search the list for a match --- * + else if ((l->type & clNode_mask) == clNode_immed) { + class_node *tn; + unsigned tt; + + tn = l, l = r, r = tn; + tt = lnode, lnode = rnode, rnode = tt; + } + + /* --- Now merge @r@ with @l@ --- */ + + l = class_mod(l); + + switch (op) { + + /* --- The union operation isn't hard --- */ + + case clNode_union: + if (rnode == clNode_immed) { + if (type & clType_user) { + sym_find(&l->v.t, (char *)&r->v.u, + sizeof(r->v.u), sizeof(sym_base), 0); + } else + sym_find(&l->v.t, r->v.s, -1, sizeof(sym_base), 0); + } else { + sym_iter i; + sym_base *b; + + for (sym_createIter(&i, &r->v.t); (b = sym_next(&i)) != 0; ) + sym_find(&l->v.t, b->name, b->len, sizeof(sym_base), 0); + } + break; + + /* --- Set difference is similar in spirit --- */ + + case clNode_diff: + if (rnode == clNode_immed) { + sym_base *f; + + if (type & clType_user) + f = sym_find(&l->v.t, (char *)&r->v.u, sizeof(r->v.u), 0, 0); + else + f = sym_find(&l->v.t, r->v.s, -1, 0, 0); + if (f) + sym_remove(&l->v.t, f); + } else { + sym_iter i; + sym_base *b, *f; + + for (sym_createIter(&i, &r->v.t); (b = sym_next(&i)) != 0; ) { + if ((f = sym_find(&l->v.t, b->name, b->len, 0, 0)) != 0) + sym_remove(&l->v.t, f); + } + } + break; + + /* --- Intersection is wild and wacky --- */ + + case clNode_isect: + if (rnode == clNode_immed) { + sym_base *f; + + if (type & clType_user) + f = sym_find(&l->v.t, (char *)&r->v.u, sizeof(r->v.u), 0, 0); + else + f = sym_find(&l->v.t, r->v.s, -1, 0, 0); + if (f) { + class_dec(l); + return (r); + } else { + class_dec(l); + class_dec(r); + return (class_none); + } + } else { + sym_iter i; + sym_base *b; + + for (sym_createIter(&i, &l->v.t); (b = sym_next(&i)) != 0; ) { + if (!sym_find(&r->v.t, b->name, b->len, 0, 0)) + sym_remove(&l->v.t, b); + } + } + break; + } + + /* --- Now trim the @l@ table to size --- * * - * This is almost infinitely slow, I'm afraid. + * It may have lost a load of elements. Maybe it can be represented + * better as an immediate or even as @class_none@. */ - for (sym_createIter(&i, c->t); (s = sym_next(&i)) != 0; ) { + { + sym_iter i; + sym_base *b; - /* --- Check the dotted-quad name first --- */ + class_dec(r); - if (class__wildMatch(s->name, a)) { - T( trace(TRACE_CHECK, "check: host address `%s' matched by `%s'", - a, s->name); ) - return (1); + sym_createIter(&i, &l->v.t); + if ((b = sym_next(&i)) == 0) { + class_dec(l); + return (class_none); } + if (!sym_next(&i)) { + if (type & clType_user) { + uid_t u = *(uid_t *)b->name; + sym_destroyTable(&l->v.t); + l->type = (l->type & ~clNode_mask) | clNode_immed; + l->v.u = u; + } else { + char *s = xstrdup(b->name); + sym_destroyTable(&l->v.t); + l->type = (l->type & ~clNode_mask) | clNode_immed; + l->v.s = s; + } + } + } + + /* --- Done --- */ + + return (l); + } + + /* --- Unfriendly nodes --- * + * + * Create a binop node and return that. If @l@ is a binop node, and @r@ + * isn't, and the operation isn't set difference (i.e., it's commutative) + * then swap the two over to lessen the depth of recursion later. + */ + + else { + class_node *c = xmalloc(sizeof(*c)); + + c->type = type | op; + c->ref = 1; + if (lnode >= clNode_binop && rnode < clNode_binop && op != clNode_diff) { + c->v.c.l = r; + c->v.c.r = l; + } else { + c->v.c.l = l; + c->v.c.r = r; + } + return (c); + } +} + +/* --- @class_union@ --- * + * + * Arguments: @class_node *l@ = left argument + * @class_node *r@ = right argument + * + * Returns: A class node representing the union of the two classes. + * + * Use: Performs the union operation on classes. If the types don't + * match, then a null pointer is returned. Both @l@ and @r@ + * may be modified, and will be decremented before they get + * returned to you. If you don't want that to happen, ensure + * that you've claimed a reference to the original versions. + */ + +class_node *class_union(class_node *l, class_node *r) +{ + /* --- Check for the really simple cases --- */ + + if (l == class_all || r == class_all) { + class_dec(l); + class_dec(r); + return (class_all); + } + + if (l == class_none) + return (r); + if (r == class_none) + return (l); - if (he) { + /* --- Do the job --- */ + + return (class__binop(l, r, clNode_union)); +} + +/* --- @class_diff@ --- * + * + * Arguments: @class_node *l@ = left argument + * @class_node *r@ = right argument + * + * Returns: A class node representing the difference of the two classes. + * + * Use: Performs the set difference operation on classes. If the + * types don't match, then a null pointer is returned. Both + * @l@ and @r@ may be modified, and will be decremented before + * they get returned to you. If you don't want that to happen, + * ensure that you've claimed a reference to the original + * versions. + */ + +class_node *class_diff(class_node *l, class_node *r) +{ + /* --- Check for the really simple cases --- */ + + if (l == class_none || r == class_all) { + class_dec(l); + class_dec(r); + return (class_none); + } - /* --- Now try the host's main name --- */ + if (r == class_none) + return (l); - if (class__wildMatch(s->name, he->h_name)) { - T( trace(TRACE_CHECK, "check: host name `%s' matched by `%s'", - he->h_name, s->name); ) + /* --- Do the job --- */ + + return (class__binop(l, r, clNode_diff)); +} + +/* --- @class_isect@ --- * + * + * Arguments: @class_node *l@ = left argument + * @class_node *r@ = right argument + * + * Returns: A class node representing the intersection of the two + * classes. + * + * Use: Performs the intersecion operation on classes. If the types + * don't match, then a null pointer is returned. Both @l@ and + * @r@ may be modified, and will be decremented before they get + * returned to you. If you don't want that to happen, ensure + * that you've claimed a reference to the original versions. + */ + +class_node *class_isect(class_node *l, class_node *r) +{ + /* --- Check for the really simple cases --- */ + + if (l == class_none || r == class_none) { + class_dec(l); + class_dec(r); + return (class_none); + } + + if (l == class_all) + return (r); + if (r == class_all) + return (l); + + /* --- Do the job --- */ + + return (class__binop(l, r, clNode_isect)); +} + +/*----- Building the predefined classes -----------------------------------*/ + +/* --- @class_addUser@ --- * + * + * Arguments: @class_node *c@ = pointer to a class node (may be null) + * @uid_t u@ = user id number + * + * Returns: Pointer to the combined node. + * + * Use: Adds a user to a node, maybe hashifying it. + */ + +class_node *class_addUser(class_node *c, uid_t u) +{ + if (!c) + return (class_fromUser(clType_user, u)); + if ((c->type & clNode_mask) == clNode_immed) + c = class__hashify(c); + sym_find(&c->v.t, (char *)&u, sizeof(u), sizeof(sym_base), 0); + return (c); +} + +/* --- @class_addString@ --- * + * + * Arguments: @class_node *c@ = pointer to a class node (may be null) + * @const char *s@ = pointer to a string + * + * Returns: Pointer to the combined node. + * + * Use: Adds a user to a node, maybe hashifying it. + */ + +class_node *class_addString(class_node *c, const char *s) +{ + class_node *n = class_fromString(clType_host, s); /* hack */ + if (c) + return (class_union(c, n)); + else + return (n); +} + +/*----- Matching functions ------------------------------------------------*/ + +/* --- @class_matchUser@ --- * + * + * Arguments: @class_node *c@ = pointer to root class node + * @uid_t u@ = user id number + * + * Returns: Nonzero if it matches, zero if it doesn't. + * + * Use: Determines whether a user is matched by a class. Assumes + * that the types are correct. + */ + +int class_matchUser(class_node *c, uid_t u) +{ + class_node *cc; + + for (cc = 0; c; c = cc, cc = 0) { + if (c == class_none) + return (0); + if (c == class_all) + return (1); + switch (c->type & clNode_mask) { + case clNode_immed: + return (u == c->v.u); + break; + case clNode_hash: + return (sym_find(&c->v.t, (char *)&u, sizeof(u), 0, 0) != 0); + break; + case clNode_union: + if (class_matchUser(c->v.c.l, u)) return (1); - } + cc = c->v.c.r; + break; + case clNode_isect: + if (!class_matchUser(c->v.c.l, u)) + return (0); + cc = c->v.c.r; + break; + case clNode_diff: + return (class_matchUser(c->v.c.l, u) && + !class_matchUser(c->v.c.r, u)); + break; + } + } + + die("internal error: can't get here in class_matchUser"); + return (0); +} + +/* --- @class_matchCommand@ --- * + * + * Arguments: @class_node *c@ = pointer to root class node + * @const char *s@ = pointer to a string + * + * Returns: Nonzero if it matches, zero if it doesn't. + * + * Use: Determines whether a string is matched by a class. Assumes + * that the types are correct. + */ + +int class_matchCommand(class_node *c, const char *s) +{ + class_node *cc; - /* --- Now go through all the names --- */ + for (cc = 0; c; c = cc, cc = 0) { + if (c == class_none) + return (0); + if (c == class_all) + return (1); + switch (c->type & clNode_mask) { + case clNode_immed: + return (class__wildMatch(c->v.s, s)); + break; + case clNode_hash: + return (sym_find(&c->v.t, s, -1, 0, 0) != 0); + break; + case clNode_union: + if (class_matchCommand(c->v.c.l, s)) + return (1); + cc = c->v.c.r; + break; + case clNode_isect: + if (!class_matchCommand(c->v.c.l, s)) + return (0); + cc = c->v.c.r; + break; + case clNode_diff: + return (class_matchCommand(c->v.c.l, s) && + !class_matchCommand(c->v.c.r, s)); + break; + } + } + + die("internal error: can't get here in class_matchCommand"); + return (0); +} + +/* --- @class_matchHost@ --- * + * + * Arguments: @class_node *c@ = pointer to root class node + * @struct in_addr a@ = IP address to match + * + * Returns: Nonzero if it matches, zero if it doesn't. + * + * Use: Determines whether a host matches a host class. Assumes + * that the types are correct. The actual mechanism is a bit + * odd here, but I think this is the Right Thing. At each stage + * I try to match %%@/all/%% of the possible names for the host. + * Thus host `splat' with address 1.2.3.4 would fail to match + * the class "1.2.*" - "splat". This seems to be what the + * author intuitively expects. It's just a bit weird. + */ + +static int class__doMatchHost(class_node *c, const char *ip, + const char *name, char **aliases) +{ + class_node *cc; - for (p = he->h_aliases; *p; p++) { - if (class__wildMatch(s->name, *p)) { - T( trace(TRACE_CHECK, "check: host alias `%s' matched by `%s'", - *p, s->name); ) + for (cc = 0; c; c = cc, cc = 0) { + if (c == class_none) + return (0); + if (c == class_all) + return (1); + switch (c->type & clNode_mask) { + case clNode_immed: + if ((ip && class__wildMatch(c->v.s, ip)) || + (name && class__wildMatch(c->v.s, name))) + return (1); + if (aliases) for (; *aliases; aliases++) { + if (class__wildMatch(c->v.s, *aliases)) return (1); - } } - } + return (0); + break; + case clNode_hash: + if ((ip && sym_find(&c->v.t, ip, -1, 0, 0)) || + (name && sym_find(&c->v.t, name, -1, 0, 0))) + return (1); + if (aliases) for (; *aliases; aliases++) { + if (sym_find(&c->v.t, *aliases, -1, 0, 0)) + return (1); + } + return (0); + break; + case clNode_union: + if (class__doMatchHost(c->v.c.l, ip, name, aliases)) + return (1); + cc = c->v.c.r; + break; + case clNode_isect: + if (!class__doMatchHost(c->v.c.l, ip, name, aliases)) + return (0); + cc = c->v.c.r; + break; + case clNode_diff: + return (class__doMatchHost(c->v.c.l, ip, name, aliases) && + !class__doMatchHost(c->v.c.r, ip, name, aliases)); + break; } + } - T( trace(TRACE_CHECK, "check: couldn't match hostname `%s'", - he->h_name); ) - return (0); + die("internal error: can't get here in class_matchUser"); + return (0); +} + +int class_matchHost(class_node *c, struct in_addr a) +{ + char *ip, *name, **aliases; + struct hostent *h; + + ip = inet_ntoa(a); + if ((h = gethostbyaddr((char *)&a, sizeof(a), AF_INET)) != 0) { + name = h->h_name; + aliases = h->h_aliases; + } else { + name = 0; + aliases = 0; } + + return (class__doMatchHost(c, ip, name, aliases)); } +/*----- Debugging code ----------------------------------------------------*/ + /* --- @class_dump@ --- * * - * Arguments: @classdef *c@ = pointer to a class block + * Argumemnts: @class_node *c@ = pointer to root node + * @int indent@ = indent depth * * Returns: --- * - * Use: Dumps the contents of a class to a stream. + * Use: Dumps a class to the trace output. */ -void class_dump(classdef *c) +void class_dump(class_node *c, int indent) { #ifdef TRACING - sym_iter i; - sym_base *s; - - /* --- Dump the table --- */ - - if (c->type != clType_all) { - for (sym_createIter(&i, c->t); (s = sym_next(&i)) != 0; ) { - switch (c->type) { - case clType_user: - trace(TRACE_RULE, " %i", *(int *)s->name); - break; - case clType_command: - case clType_host: - trace(TRACE_RULE, " `%s'", s->name); - break; + + static char *types[] = { + "", + "user", + "command", + "", + "host" + }; + + static char *nodes[] = { + "", + "", + "immediate", + "hash", + "binop: union", + "binop: difference", + "binop: intersection" + }; + + /* --- Handle some magical cases --- */ + + if (c == class_all) { + trace(TRACE_RULE, "rule:%*s class ALL", indent * 2, ""); + return; + } + if (c == class_none) { + trace(TRACE_RULE, "rule:%*s class NONE", indent * 2, ""); + return; + } + + /* --- Dump basic type information --- */ + + trace(TRACE_RULE, "rule:%*s type == [%s], node type == [%s]%s", + indent * 2, "", + types[c->type & clType_mask], + nodes[(c->type & clNode_mask) >> 4], + (c->type & clFlag_friendly) ? " Friendly" : ""); + + /* --- Now trace the contents --- */ + + switch (c->type & clNode_mask) { + case clNode_immed: + if (c->type & clType_user) { + trace(TRACE_RULE, "rule:%*s user %lu", + indent * 2, "", (unsigned long)c->v.u); + } else + trace(TRACE_RULE, "rule:%*s `%s'", indent * 2, "", c->v.s); + break; + case clNode_hash: { + sym_iter i; + sym_base *b; + + for (sym_createIter(&i, &c->v.t); (b = sym_next(&i)) != 0; ) { + if (c->type & clType_user) { + trace(TRACE_RULE, "rule:%*s user %lu", + indent * 2, "", (unsigned long)*(uid_t *)b->name); + } else + trace(TRACE_RULE, "rule:%*s `%s'", indent * 2, "", b->name); } - } + } break; + case clNode_union: + case clNode_diff: + case clNode_isect: + class_dump(c->v.c.l, indent + 1); + class_dump(c->v.c.r, indent + 1); + break; } - else - trace(TRACE_RULE, " ALL"); + #endif } diff --git a/src/class.h b/src/class.h index 9abbe3f..6cf53a5 100644 --- a/src/class.h +++ b/src/class.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: class.h,v 1.2 1997/08/04 10:24:21 mdw Exp $ + * $Id: class.h,v 1.3 1997/09/17 10:14:56 mdw Exp $ * * Handling classes of things nicely * @@ -29,6 +29,10 @@ /*----- Revision history --------------------------------------------------* * * $Log: class.h,v $ + * Revision 1.3 1997/09/17 10:14:56 mdw + * Complete rewrite to support class trees. Makes the behaviour of the set + * operators much more logical. + * * Revision 1.2 1997/08/04 10:24:21 mdw * Sources placed under CVS control. * @@ -60,112 +64,254 @@ /* --- Class types --- */ enum { - clType_user = 1, /* Class of users */ - clType_command = 2, /* Class of command strings */ - clType_host = 4, /* Class of host names */ - clType_all = 7, /* All of the above (maintain me) */ - clType__limit /* First undefined class type */ + + /* --- Data types (user visible) --- * + * + * These bits encode what the user can think of as `types'. They get used + * for typechecking and things. + */ + + clType_user = 0x01, /* Class of users */ + clType_command = 0x02, /* Class of command strings */ + clType_host = 0x04, /* Class of host names */ + clType_all = 0x0F, /* All of the above (maintain me) */ + clType_mask = 0x0F, /* Mask for type flags */ + + /* --- Node types --- * + * + * A class actually looks suspiciously like a tree once things start + * getting complicated. These bits encode the type of node we've got here. + */ + + clNode_any = 0x10, /* Magic type for the `all' class */ + clNode_immed = 0x20, /* Immediate data item */ + clNode_hash = 0x30, /* Hashtable of values */ + clNode_union = 0x40, /* Union of two classes */ + clNode_binop = 0x50, /* Binary operations start here */ + clNode_diff = 0x50, /* Difference of two classes */ + clNode_isect = 0x60, /* Intersection of two classes */ + clNode_mask = 0xF0, /* Mask for picking these out */ + + /* --- Other useful flags --- */ + + clFlag_friendly = 0x100 /* Item can be hashed with others */ }; /* --- Class block --- */ -typedef struct classdef { - unsigned type; /* Type of this class */ +typedef struct class_node { + unsigned type; /* Class and node type, and flags */ unsigned ref; /* Reference count */ - sym_table *t; /* Symbol table for this class */ -} classdef; + union { + uid_t u; /* Immediate user id number */ + char *s; /* Immediate string value */ + sym_table t; /* Hash table for this class */ + struct { + struct class_node *l, *r; /* Left and right operands */ + } c; /* Class operands for binops */ + } v; /* Value of this class node */ +} class_node; /*----- Global variables --------------------------------------------------*/ -extern classdef *class_all; /* The match-everything class */ +extern class_node *class_all; /* The match-everything class */ +extern class_node *class_none; /* The match-nothing class */ /*----- Functions provided ------------------------------------------------*/ -/* --- @class_create@ --- * +/* --- @class_fromString@ --- * * - * Arguments: @unsigned type@ = type of the class to create - * @sym_table *t@ = pointer to symbol table which stores info + * Arguments: @unsigned type@ = a type field + * @const char *s@ = pointer to string to copy * - * Returns: Pointer to a @classdef@ which maintains the class's info. + * Returns: A pointer to a class node containing that string, typed to + * be the right thing. * - * Use: Creates a new class definition. The new definition has one - * reference attached to it (which is the one you get returned). + * Use: Given a string, wrap a class node around it. The node has + * one reference (the one you get returned). The string is + * copied, so you can get rid of your original one if you like. */ -extern classdef *class_create(unsigned /*type*/, sym_table */*t*/); +extern class_node *class_fromString(unsigned /*type*/, const char */*s*/); + +/* --- @class_fromUser@ --- * + * + * Arguments: @unsigned type@ = a type field + * @uid_t u@ = a user-id number + * + * Returns: A pointer to a class node containing the uid, typed to be + * the thing you asked for. Hopefully this will be + * @clType_user@. + * + * Use: Given a uid, wrap a class node around it. + */ + +extern class_node *class_fromUser(unsigned /*type*/, uid_t /*u*/); /* --- @class_inc@ --- * * - * Arguments: @classdef *c@ = pointer to a class block + * Arguments: @class_node *c@ = pointer to a class block * * Returns: --- * * Use: Adds a reference to the class definition. */ -extern void class_inc(classdef */*c*/); +extern void class_inc(class_node */*c*/); /* --- @class_dec@ --- * * - * Arguments: @classdef *c@ = pointer to a class block + * Arguments: @class_node *c@ = pointer to a class block * * Returns: --- * * Use: Removes a reference to a class block. */ -extern void class_dec(classdef */*c*/); +extern void class_dec(class_node */*c*/); + +/* --- @class_mod@ --- * + * + * Arguments: @class_node *c@ = pointer to a class node + * + * Returns: A pointer to a class node, maybe the same one, maybe not, + * with a reference count of 1, containing the same data. + * + * Use: Gives you a node which you can modify. Don't call this + * for @class_all@ or @class_none@. + */ + +extern class_node *class_mod(class_node */*c*/); + +/* --- @class_union@ --- * + * + * Arguments: @class_node *l@ = left argument + * @class_node *r@ = right argument + * + * Returns: A class node representing the union of the two classes. + * + * Use: Performs the union operation on classes. If the types don't + * match, then a null pointer is returned. Both @l@ and @r@ + * may be modified, and will be decremented before they get + * returned to you. If you don't want that to happen, ensure + * that you've claimed a reference to the original versions. + */ + +extern class_node *class_union(class_node */*l*/, class_node */*r*/); + +/* --- @class_diff@ --- * + * + * Arguments: @class_node *l@ = left argument + * @class_node *r@ = right argument + * + * Returns: A class node representing the difference of the two classes. + * + * Use: Performs the set difference operation on classes. If the + * types don't match, then a null pointer is returned. Both + * @l@ and @r@ may be modified, and will be decremented before + * they get returned to you. If you don't want that to happen, + * ensure that you've claimed a reference to the original + * versions. + */ + +extern class_node *class_diff(class_node */*l*/, class_node */*r*/); + +/* --- @class_isect@ --- * + * + * Arguments: @class_node *l@ = left argument + * @class_node *r@ = right argument + * + * Returns: A class node representing the intersection of the two + * classes. + * + * Use: Performs the intersecion operation on classes. If the types + * don't match, then a null pointer is returned. Both @l@ and + * @r@ may be modified, and will be decremented before they get + * returned to you. If you don't want that to happen, ensure + * that you've claimed a reference to the original versions. + */ + +extern class_node *class_isect(class_node */*l*/, class_node */*r*/); + +/* --- @class_addUser@ --- * + * + * Arguments: @class_node *c@ = pointer to a class node (may be null) + * @uid_t u@ = user id number + * + * Returns: Pointer to the combined node. + * + * Use: Adds a user to a node, maybe hashifying it. + */ + +extern class_node *class_addUser(class_node */*c*/, uid_t /*u*/); + +/* --- @class_addString@ --- * + * + * Arguments: @class_node *c@ = pointer to a class node (may be null) + * @const char *s@ = pointer to a string + * + * Returns: Pointer to the combined node. + * + * Use: Adds a user to a node, maybe hashifying it. + */ + +extern class_node *class_addString(class_node */*c*/, const char */*s*/); -/* --- @class_userMatch@ --- * +/* --- @class_matchUser@ --- * * - * Arguments: @classdef *c@ = pointer to a class block - * @int u@ = uid number to check against + * Arguments: @class_node *c@ = pointer to root class node + * @uid_t u@ = user id number * - * Returns: Zero if no match, nonzero if it matched. + * Returns: Nonzero if it matches, zero if it doesn't. * - * Use: Looks to see if a user is in a group. + * Use: Determines whether a user is matched by a class. Assumes + * that the types are correct. */ -extern int class_userMatch(classdef */*c*/, int /*u*/); +extern int class_matchUser(class_node */*c*/, uid_t /*u*/); -/* --- @class_commandMatch@ --- * +/* --- @class_matchCommand@ --- * * - * Arguments: @classdef *c@ = pointer to a class block - * @const char *p@ = pointer to command string to match + * Arguments: @class_node *c@ = pointer to root class node + * @const char *s@ = pointer to a string * - * Returns: Zero for no match, nonzero if it matched. + * Returns: Nonzero if it matches, zero if it doesn't. * - * Use: Tries to match a string against the wildcard patterns in the - * given class. Note that this involves examining all the - * items, so it's not too quick. Then again, you don't have - * big command classes, do you...? + * Use: Determines whether a string is matched by a class. Assumes + * that the types are correct. */ -extern int class_commandMatch(classdef */*c*/, const char */*p*/); +extern int class_matchCommand(class_node */*c*/, const char */*s*/); -/* --- @class_hostMatch@ --- * +/* --- @class_matchHost@ --- * * - * Arguments: @classdef *c@ = pointer to class block - * @struct in_addr addr@ = IP address to match + * Arguments: @class_node *c@ = pointer to root class node + * @struct in_addr a@ = IP address to match * - * Returns: Zero for no match, nonzero if it matched. + * Returns: Nonzero if it matches, zero if it doesn't. * - * Use: Tries to match an IP address against the patterns and masks - * in the given class. + * Use: Determines whether a host matches a host class. Assumes + * that the types are correct. The actual mechanism is a bit + * odd here, but I think this is the Right Thing. At each stage + * I try to match %%@/all/%% of the possible names for the host. + * Thus host `splat' with address 1.2.3.4 would fail to match + * the class "1.2.*" - "splat". This seems to be what the + * author intuitively expects. It's just a bit weird. */ -extern int class_hostMatch(classdef */*c*/, struct in_addr /*addr*/); +extern int class_matchHost(class_node */*c*/, struct in_addr /*a*/); /* --- @class_dump@ --- * * - * Arguments: @classdef *c@ = pointer to a class block + * Argumemnts: @class_node *c@ = pointer to root node + * @int indent@ = indent depth * * Returns: --- * - * Use: Dumps the contents of a class to a stream. + * Use: Dumps a class to the trace output. */ -extern void class_dump(classdef */*c*/); +extern void class_dump(class_node */*c*/, int /*indent*/); /*----- That's all, folks -------------------------------------------------*/ -- 2.11.0