/*
- * Copyright (c) 2012, JANET(UK)
+ * Copyright (c) 2012-2018, JANET(UK)
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
*
*/
+#include <stdio.h>
#include <jansson.h>
#include <talloc.h>
#include <sys/time.h>
#include <tr_rp.h>
#include <tr_idp.h>
-#include <trust_router/tr_name.h>
+#include <tr_name_internal.h>
+#include <trp_internal.h>
#include <tr_comm.h>
#include <tr_debug.h>
-
-
-/* static prototypes */
-static TR_NAME *tr_comm_memb_get_realm_id(TR_COMM_MEMB *memb);
-
+#include <tr_util.h>
static int tr_comm_destructor(void *obj)
{
return comm->refcount;
}
-/* add to the table if it's a new membership or has a shorter
- * provenance list than our existing membership */
+/* 0 if equivalent, nonzero if different, only considers
+ * nhops last hops (nhops==0 means consider all, nhops==1
+ * only considers last hop) */
+static int tr_comm_memb_provenance_cmp(TR_COMM_MEMB *m1, TR_COMM_MEMB *m2, int nhops)
+{
+ size_t ii;
+
+ if ((m1->provenance==NULL) || (m2->provenance==NULL))
+ return m1->provenance!=m2->provenance; /* return 0 if both null, 1 if only one null */
+
+ if (json_array_size(m1->provenance)!=json_array_size(m2->provenance))
+ return 1;
+
+ if (nhops==0)
+ nhops=json_array_size(m1->provenance); /* same as size(m2->provenance) */
+
+ for (ii=0; ii<json_array_size(m1->provenance); ii++) {
+ if (0==strcmp(json_string_value(json_array_get(m1->provenance, ii)),
+ json_string_value(json_array_get(m2->provenance, ii)))) {
+ return 0;
+ }
+ }
+ return 1;
+}
+
+/* Accepts an update that either came from the same peer as the previous
+ * origin, has a shorter provenance list, or can replace an expired
+ * membership. Otherwise keeps the existing one.
+ * On replacement, frees the old member and moves new member to ctab's
+ * context. Caller should not free newmemb except by freeing its original
+ * context. */
static void tr_comm_add_if_shorter(TR_COMM_TABLE *ctab, TR_COMM_MEMB *existing, TR_COMM_MEMB *newmemb)
{
+ int accept=0;
+
if (existing==NULL) {
/* not in the table */
tr_comm_table_add_memb(ctab, newmemb);
} else {
- /* Had an entry. Replace if we have shorter provenance. */
- if (tr_comm_memb_provenance_len(newmemb) < tr_comm_memb_provenance_len(existing)) {
+ if (0==tr_comm_memb_provenance_cmp(existing, newmemb, 1))
+ accept=1; /* always accept a replacement from the same peer */
+ else if (tr_comm_memb_provenance_len(newmemb) < tr_comm_memb_provenance_len(existing))
+ accept=1; /* accept a shorter provenance */
+ else if (existing->times_expired>0)
+ accept=1;
+ else
+ accept=0;
+
+ if (accept) {
tr_comm_table_remove_memb(ctab, existing);
tr_comm_memb_free(existing);
tr_comm_table_add_memb(ctab, newmemb);
- }
+ }
}
}
void tr_comm_add_idp_realm(TR_COMM_TABLE *ctab,
TR_COMM *comm,
TR_IDP_REALM *realm,
+ unsigned int interval,
json_t *provenance,
struct timespec *expiry)
{
tr_comm_memb_set_idp_realm(newmemb, realm);
tr_comm_memb_set_comm(newmemb, comm);
+ tr_comm_memb_set_interval(newmemb, interval);
tr_comm_memb_set_provenance(newmemb, provenance);
tr_comm_memb_set_expiry(newmemb, expiry);
tr_comm_get_id(comm),
tr_comm_memb_get_origin(newmemb));
tr_comm_add_if_shorter(ctab, existing, newmemb); /* takes newmemb out of tmp_ctx if needed */
+
talloc_free(tmp_ctx);
}
void tr_comm_add_rp_realm(TR_COMM_TABLE *ctab,
TR_COMM *comm,
TR_RP_REALM *realm,
+ unsigned int interval,
json_t *provenance,
struct timespec *expiry)
{
tr_comm_memb_set_rp_realm(newmemb, realm);
tr_comm_memb_set_comm(newmemb, comm);
+ tr_comm_memb_set_interval(newmemb, interval);
tr_comm_memb_set_provenance(newmemb, provenance);
tr_comm_memb_set_expiry(newmemb, expiry);
* the list head was in. */
comms=comms->next;
if (comms!=NULL) {
- talloc_steal(list_ctx, comms->next);
+ talloc_steal(list_ctx, comms);
/* now put all the other elements in the context of the list head */
for (this=comms->next; this!=NULL; this=this->next)
talloc_steal(comms, this);
} else {
/* not removing the head; no need to play with contexts */
for (this=comms; this->next!=NULL; this=this->next) {
- if (this->next==remove)
+ if (this->next==remove) {
this->next=remove->next;
+ break;
+ }
}
}
return comms;
}
+/* remove any with zero refcount
+ * Call via macro. */
+#define tr_comm_sweep(head) ((head)=tr_comm_sweep_func((head)))
+static TR_COMM *tr_comm_sweep_func(TR_COMM *head)
+{
+ TR_COMM *comm=NULL;
+ TR_COMM *old_next=NULL;
+
+ if (head==NULL)
+ return NULL;
+
+ while ((head!=NULL) && (head->refcount==0)) {
+ comm=head; /* keep a pointer so we can remove it */
+ tr_comm_remove(head, comm); /* use this to get talloc contexts right */
+ tr_comm_free(comm);
+ }
+
+ if (head==NULL)
+ return NULL;
+
+ /* will not remove the head here, that has already been done */
+ for (comm=head; (comm!=NULL) && (comm->next!=NULL); comm=comm->next) {
+ if (comm->next->refcount==0) {
+ old_next=comm->next;
+ tr_comm_remove(head, comm->next); /* changes comm->next, may make it null */
+ tr_comm_free(old_next);
+ }
+ }
+
+ return head;
+}
+
TR_IDP_REALM *tr_comm_find_idp(TR_COMM_TABLE *ctab, TR_COMM *comm, TR_NAME *idp_realm)
{
TALLOC_CTX *tmp_ctx=talloc_new(NULL);
if (iter!=NULL) {
iter->cur_comm=NULL;
iter->cur_memb=NULL;
+ iter->cur_orig_head=NULL;
iter->match=NULL;
iter->realm=NULL;
}
return s;
}
+/* iterate along the origin list for this member */
TR_COMM_MEMB *tr_comm_memb_iter_first(TR_COMM_ITER *iter, TR_COMM_MEMB *memb)
{
iter->cur_memb=memb;
return iter->cur_memb;
}
+
+/* iterate over all memberships in the table
+ *
+ * The table is structured as a vertical list of memberships, each for a
+ * different community/realm. Each element in this list has a horizontal "origin list,"
+ * each for the same community/realm but with a different origin for the membership.
+ * Only the first element in the origin list has a vertical link ("next" pointer).
+ * Any element may have a horizontal link ("origin_next" pointer).
+ *
+ * (A) - (B) - (C) - X
+ * |
+ * (D) - (E) - X
+ * |
+ * (F) - X
+ * |
+ * (G) - (H) - X
+ * |
+ * X
+ *
+ * A, B, and C are all community/realm pair membership 1, with different origins
+ * D, E are a second community/realm pair, with different origins
+ * F is a third...
+ * G, H are a fourth pair, with different origins
+ *
+ * This iterator will return every element in the grid.
+ *
+ * Algorithm:
+ * The iterator struct stores the current member (cur_memb) and the origin head (cur_orig_head).
+ * The latter is a pointer to the head of the current origin list (i.e., first element in a row).
+ * The former can point to any element in the list. Both start at the root of the list (A in the
+ * diagram above).
+ *
+ * After each call to _first() or _next(), cur_memb points to the element just returned.
+ *
+ * 0. _first() just returns the first element. The rest of the steps are in _next()
+ *
+ * 1. If cur_memb has an origin_next element, walk the origin list. Move cur_memb to
+ * the origin_list element (next one in this row) and return it.
+ * 2. If cur_memb does not have an origin_next element, we've finished the current origin
+ * list. Move cur_memb to cur_orig_head's next element (the start of the next column),
+ * move cur_orig_head to that same place, and return it.
+ * 3. If neither cur_memb has an origin_next element nor cur_orig_head has a next element,
+ * then we have already reached the end of the list and there's nothing more to do.
+ * Return NULL.
+ */
+TR_COMM_MEMB *tr_comm_memb_iter_all_first(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab)
+{
+ /* step 0: return the root of the list */
+ iter->cur_memb=ctab->memberships;
+ iter->cur_orig_head=ctab->memberships;
+ return iter->cur_memb;
+}
+
+TR_COMM_MEMB *tr_comm_memb_iter_all_next(TR_COMM_ITER *iter)
+{
+ if (iter->cur_memb->origin_next) {
+ /* step 1: return the next element in the current origin list */
+ iter->cur_memb = iter->cur_memb->origin_next;
+ } else if (iter->cur_orig_head->next) {
+ /* step 2: move to the start of the next row and return the first element */
+ iter->cur_orig_head = iter->cur_memb = iter->cur_orig_head->next;
+ } else {
+ /* step 3: both cur_memb->origin_next and cur_orig_head->next are null */
+ iter->cur_orig_head = iter->cur_memb = NULL;
+ }
+ return iter->cur_memb;
+}
+
+
TR_COMM_TYPE tr_comm_type_from_str(const char *s)
{
if (strcmp(s, "apc")==0)
memb->origin=NULL;
memb->provenance=NULL;
memb->interval=0;
+ memb->triggered=0;
+ memb->times_expired=0;
memb->expiry=talloc(memb, struct timespec);
if (memb->expiry==NULL) {
talloc_free(memb);
return NULL;
}
*(memb->expiry)=(struct timespec){0,0};
- talloc_set_destructor(memb, tr_comm_memb_destructor);
+ talloc_set_destructor((void *)memb, tr_comm_memb_destructor);
}
return memb;
}
talloc_free(memb);
}
+/* Returns 0 if they are the same, nonzero if they differ.
+ * Ignores expiry, triggered, and times_expired, next pointers */
+int tr_comm_memb_cmp(TR_COMM_MEMB *m1, TR_COMM_MEMB *m2)
+{
+ if ((m1->idp==m2->idp) &&
+ (m1->rp==m2->rp) &&
+ (m1->comm==m2->comm) &&
+ (tr_comm_memb_provenance_cmp(m1, m2, 0)==0) &&
+ (m1->interval==m2->interval))
+ return 0;
+ return 1;
+}
+
TR_REALM_ROLE tr_comm_memb_get_role(TR_COMM_MEMB *memb)
{
if (memb->rp!=NULL)
void tr_comm_memb_set_provenance(TR_COMM_MEMB *memb, json_t *prov)
{
+ const char *s=NULL;
+
if (memb->provenance)
json_decref(memb->provenance);
/* next line sets origin to NULL if provenance is empty because jansson
* routines return NULL on error */
- memb->origin=tr_new_name(json_string_value(json_array_get(prov, 0)));
+ s=json_string_value(json_array_get(prov, 0));
+ if (s==NULL)
+ tr_comm_memb_set_origin(memb, NULL);
+ else
+ memb->origin=tr_new_name(s);
} else {
tr_comm_memb_set_origin(memb, NULL);
}
void tr_comm_memb_set_expiry(TR_COMM_MEMB *memb, struct timespec *time)
{
- memb->expiry->tv_sec=time->tv_sec;
- memb->expiry->tv_nsec=time->tv_nsec;
+ if (time==NULL)
+ *(memb->expiry)=(struct timespec){0,0};
+ else {
+ memb->expiry->tv_sec=time->tv_sec;
+ memb->expiry->tv_nsec=time->tv_nsec;
+ }
}
struct timespec *tr_comm_memb_get_expiry(TR_COMM_MEMB *memb)
return memb->expiry;
}
+/**
+ * Get the expiration according to the realtime clock
+ *
+ * @param memb
+ * @param result space to store the result
+ * @return pointer to the result, or null on error
+ */
+struct timespec *tr_comm_memb_get_expiry_realtime(TR_COMM_MEMB *memb, struct timespec *result)
+{
+ return tr_clock_convert(TRP_CLOCK, memb->expiry, CLOCK_REALTIME, result);
+}
+
int tr_comm_memb_is_expired(TR_COMM_MEMB *memb, struct timespec *curtime)
{
+ tr_debug("tr_comm_memb_is_expired: (cur->tv_sec>memb->expiry->tv_sec)=(%u > %u)=%s",
+ curtime->tv_sec,
+ memb->expiry->tv_sec,
+ (curtime->tv_sec > memb->expiry->tv_sec)?"true":"false");
+
return ((curtime->tv_sec > memb->expiry->tv_sec)
|| ((curtime->tv_sec == memb->expiry->tv_sec)
&&(curtime->tv_nsec >= memb->expiry->tv_nsec)));
}
+void tr_comm_memb_set_triggered(TR_COMM_MEMB *memb, int trig)
+{
+ memb->triggered=trig;
+}
+
+int tr_comm_memb_is_triggered(TR_COMM_MEMB *memb)
+{
+ return memb->triggered;
+}
+
+void tr_comm_memb_reset_times_expired(TR_COMM_MEMB *memb)
+{
+ memb->times_expired=0;
+}
+
+/* bumps the expiration count */
+void tr_comm_memb_expire(TR_COMM_MEMB *memb)
+{
+ /* avoid overflow */
+ if (memb->times_expired+1>memb->times_expired)
+ memb->times_expired++;
+}
+
+unsigned int tr_comm_memb_get_times_expired(TR_COMM_MEMB *memb)
+{
+ return memb->times_expired;
+}
+
TR_COMM_TABLE *tr_comm_table_new(TALLOC_CTX *mem_ctx)
{
TR_COMM_TABLE *ctab=talloc(mem_ctx, TR_COMM_TABLE);
{
TR_COMM_MEMB *cur=NULL;
- /* TODO: validate the member (must have valid comm and realm) */
+ /* TODO: further validate the member (must have valid comm and realm) */
+ if ((new->next!=NULL) || (new->origin_next!=NULL)) {
+ tr_debug("tr_comm_table_add_memb: attempting to add member already in a list.");
+ }
/* handle the empty list case */
if (ctab->memberships==NULL) {
/* see if it's the first member */
if (ctab->memberships==memb) {
if (memb->origin_next!=NULL) {
- memb->origin_next->next=ctab->memberships->next;
+ memb->origin_next->next=memb->next;
ctab->memberships=memb->origin_next;
} else
ctab->memberships=memb->next;
}
/* see if it's in first member's origin list */
- for (orig_cur=ctab->memberships->origin_next;
- orig_cur!=NULL;
- orig_cur=ctab->memberships->origin_next) {
- if (orig_cur==memb) {
+ for (orig_cur=ctab->memberships;
+ orig_cur->origin_next!=NULL;
+ orig_cur=orig_cur->origin_next) {
+ if (orig_cur->origin_next==memb) {
orig_cur->origin_next=memb->origin_next;
return;
}
for (cur=ctab->memberships; cur->next!=NULL; cur=cur->next) {
if (cur->next==memb) {
/* it matched an entry on the main list */
- if (memb->origin_next!=NULL) {
+ if (memb->origin_next==NULL)
+ cur->next=memb->next; /* no origin list, just drop memb */
+ else {
/* replace the entry in the main list with the next element on the origin list */
memb->origin_next->next=memb->next;
cur->next=memb->origin_next;
- } else
- cur->next=memb->next; /* no origin list, just drop memb */
+ }
return;
} else {
/* it was not on the main list, walk the origin list */
- for (orig_cur=cur; orig_cur->next!=NULL; orig_cur=orig_cur->next) {
- if (orig_cur->next==memb) {
- orig_cur->next=memb->next;
+ for (orig_cur=cur; orig_cur->origin_next!=NULL; orig_cur=orig_cur->origin_next) {
+ if (orig_cur->origin_next==memb) {
+ orig_cur->origin_next=memb->origin_next;
return; /* just drop the element from the origin list */
}
}
}
}
+ /* if we got here, cur->next was null. Still have to check the origin_next list */
+ for (orig_cur=cur; orig_cur->origin_next!=NULL; orig_cur=orig_cur->origin_next) {
+ if (orig_cur->origin_next==memb) {
+ orig_cur->origin_next=memb->origin_next;
+ return; /* just drop the element from the origin list */
+ }
+ }
}
-static TR_NAME *tr_comm_memb_get_realm_id(TR_COMM_MEMB *memb)
+TR_NAME *tr_comm_memb_get_realm_id(TR_COMM_MEMB *memb)
{
if (memb->rp!=NULL)
return tr_rp_realm_get_id(memb->rp);
return tr_comm_lookup(ctab->comms, comm_id);
}
-void tr_comm_table_add_comm(TR_COMM_TABLE *ctab, TR_COMM *new)
+/**
+ * Add a community to the table.
+ *
+ * Does not allow duplicate community ids.
+ *
+ * @param ctab
+ * @param new
+ * @return 0 on success, -1 on failure
+ */
+int tr_comm_table_add_comm(TR_COMM_TABLE *ctab, TR_COMM *new)
{
+ if (tr_comm_table_find_comm(ctab, tr_comm_get_id(new)) != NULL)
+ return -1;
+
tr_comm_add(ctab->comms, new);
+ if (ctab->comms!=NULL)
+ talloc_steal(ctab, ctab->comms); /* make sure it's in the right context */
+ return 0;
}
void tr_comm_table_remove_comm(TR_COMM_TABLE *ctab, TR_COMM *comm)
tr_comm_remove(ctab->comms, comm);
}
+TR_RP_REALM *tr_comm_table_find_rp_realm(TR_COMM_TABLE *ctab, TR_NAME *realm_id)
+{
+ return tr_rp_realm_lookup(ctab->rp_realms, realm_id);
+}
+
+void tr_comm_table_add_rp_realm(TR_COMM_TABLE *ctab, TR_RP_REALM *new)
+{
+ tr_rp_realm_add(ctab->rp_realms, new);
+ if (ctab->rp_realms!=NULL)
+ talloc_steal(ctab, ctab->rp_realms); /* make sure it's in the right context */
+}
+
+void tr_comm_table_remove_rp_realm(TR_COMM_TABLE *ctab, TR_RP_REALM *realm)
+{
+ tr_rp_realm_remove(ctab->rp_realms, realm);
+}
+
+TR_IDP_REALM *tr_comm_table_find_idp_realm(TR_COMM_TABLE *ctab, TR_NAME *realm_id)
+{
+ return tr_idp_realm_lookup(ctab->idp_realms, realm_id);
+}
+
+void tr_comm_table_add_idp_realm(TR_COMM_TABLE *ctab, TR_IDP_REALM *new)
+{
+ tr_idp_realm_add(ctab->idp_realms, new);
+ if (ctab->idp_realms!=NULL)
+ talloc_steal(ctab, ctab->idp_realms); /* make sure it's in the right context */
+}
+
+void tr_comm_table_remove_idp_realm(TR_COMM_TABLE *ctab, TR_IDP_REALM *realm)
+{
+ tr_idp_realm_remove(ctab->idp_realms, realm);
+}
+
+
/* how many communities in the table? */
size_t tr_comm_table_size(TR_COMM_TABLE *ctab)
{
return count;
}
+/* clean up unreferenced realms, etc */
+void tr_comm_table_sweep(TR_COMM_TABLE *ctab)
+{
+ tr_rp_realm_sweep(ctab->rp_realms);
+ tr_idp_realm_sweep(ctab->idp_realms);
+ tr_comm_sweep(ctab->comms);
+}
+
const char *tr_realm_role_to_str(TR_REALM_ROLE role)
{
return TR_ROLE_UNKNOWN;
}
+static char *tr_comm_table_append_provenance(char *ctable_s, json_t *prov)
+{
+ const char *s=NULL;
+ char *tmp=NULL;
+ size_t ii=0;
+
+ for (ii=0; ii<json_array_size(prov); ii++) {
+ s=json_string_value(json_array_get(prov, ii));
+ if (s!=NULL) {
+ tmp=talloc_asprintf_append(ctable_s, "%s%s", s, ((ii + 1) == json_array_size(prov)) ? "" : ", ");
+ if (tmp==NULL)
+ return NULL;
+ ctable_s=tmp;
+ }
+ }
+ return ctable_s;
+}
+
+char *tr_comm_table_to_str(TALLOC_CTX *mem_ctx, TR_COMM_TABLE *ctab)
+{
+ TALLOC_CTX *tmp_ctx=talloc_new(NULL);
+ char *ctable_s=NULL;
+ char *tmp=NULL;
+#define append_on_success_helper(tab,tmp,expr) if(NULL==((tmp)=(expr))){(tab)=NULL;goto cleanup;}(tab)=(tmp)
+
+ TR_COMM_MEMB *p1=NULL; /* for walking the main list */
+ TR_COMM_MEMB *p2=NULL; /* for walking the same-origin lists */
+
+ ctable_s=talloc_asprintf(tmp_ctx, ">> Membership table start <<\n");
+ if (ctable_s==NULL)
+ goto cleanup;
+
+ for (p1=ctab->memberships; p1!=NULL; p1=p1->next) {
+ append_on_success_helper(
+ ctable_s, tmp,
+ talloc_asprintf_append(ctable_s, "* %s %s/%s\n %s (%p) - prov: ",
+ tr_realm_role_to_str(tr_comm_memb_get_role(p1)),
+ tr_comm_memb_get_realm_id(p1)->buf,
+ tr_comm_get_id(tr_comm_memb_get_comm(p1))->buf,
+ (tr_comm_memb_get_origin(p1)==NULL)?"null origin":(tr_comm_memb_get_origin(p1)->buf),
+ p1));
+
+ append_on_success_helper(ctable_s, tmp, tr_comm_table_append_provenance(ctable_s, p1->provenance));
+
+ append_on_success_helper(ctable_s, tmp, talloc_strdup_append_buffer(ctable_s, "\n"));
+
+ for (p2=p1->origin_next; p2!=NULL; p2=p2->origin_next) {
+ append_on_success_helper(
+ ctable_s, tmp,
+ talloc_asprintf_append(ctable_s, " %s (%p) - prov: ",
+ (tr_comm_memb_get_origin(p2)==NULL)?"null origin":(tr_comm_memb_get_origin(p2)->buf),
+ p2));
+ append_on_success_helper(ctable_s, tmp, tr_comm_table_append_provenance(ctable_s, p2->provenance));
+ append_on_success_helper(ctable_s, tmp, talloc_strdup_append_buffer(ctable_s, "\n"));
+ }
+ append_on_success_helper(ctable_s, tmp, talloc_strdup_append_buffer(ctable_s, "\n"));
+ }
+
+cleanup:
+ if (ctable_s!=NULL)
+ talloc_steal(mem_ctx, ctable_s);
+
+ talloc_free(tmp_ctx);
+ return ctable_s;
+}
+
+void tr_comm_table_print(FILE *f, TR_COMM_TABLE *ctab)
+{
+ char *s=tr_comm_table_to_str(NULL, ctab);
+ if (s!=NULL) {
+ tr_debug("%s", s);
+ talloc_free(s);
+ }
+}
\ No newline at end of file