>From 0025e5d63d5d1598ab622867834a3bcb9f518f9f Mon Sep 17 00:00:00 2001 From: Stephen Hemminger Date: Thu, 28 Mar 2013 14:57:28 -0700 Subject: [PATCH 1/2] ll_map: add name and index hash Make ll_ functions faster by having a name hash, and allow for deletion. Also, allow them to work without calling ll_init_map. --- include/hlist.h | 56 ++++++++++++++++++++ include/ll_map.h | 3 +- lib/ll_map.c | 155 ++++++++++++++++++++++++++++++++++-------------------- 3 files changed, 157 insertions(+), 57 deletions(-) create mode 100644 include/hlist.h diff --git a/include/hlist.h b/include/hlist.h new file mode 100644 index 0000000..4e8de9e --- /dev/null +++ b/include/hlist.h @@ -0,0 +1,56 @@ +#ifndef __HLIST_H__ +#define __HLIST_H__ 1 +/* Hash list stuff from kernel */ + +#include + +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + +struct hlist_head { + struct hlist_node *first; +}; + +struct hlist_node { + struct hlist_node *next, **pprev; +}; + +static inline void hlist_del(struct hlist_node *n) +{ + struct hlist_node *next = n->next; + struct hlist_node **pprev = n->pprev; + *pprev = next; + if (next) + next->pprev = pprev; +} + +static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) +{ + struct hlist_node *first = h->first; + n->next = first; + if (first) + first->pprev = &n->next; + h->first = n; + n->pprev = &h->first; +} + +#define hlist_for_each(pos, head) \ + for (pos = (head)->first; pos ; pos = pos->next) + + +#define hlist_for_each_safe(pos, n, head) \ + for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ + pos = n) + +#define hlist_entry_safe(ptr, type, member) \ + ({ typeof(ptr) ____ptr = (ptr); \ + ____ptr ? hlist_entry(____ptr, type, member) : NULL; \ + }) + +#define hlist_for_each_entry(pos, head, member) \ + for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ + pos; \ + pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) + +#endif /* __HLIST_H__ */ diff --git a/include/ll_map.h b/include/ll_map.h index c4d5c6d..f1dda39 100644 --- a/include/ll_map.h +++ b/include/ll_map.h @@ -3,7 +3,8 @@ extern int ll_remember_index(const struct sockaddr_nl *who, struct nlmsghdr *n, void *arg); -extern int ll_init_map(struct rtnl_handle *rth); + +extern void ll_init_map(struct rtnl_handle *rth); extern unsigned ll_name_to_index(const char *name); extern const char *ll_index_to_name(unsigned idx); extern const char *ll_idx_n2a(unsigned idx, char *buf); diff --git a/lib/ll_map.c b/lib/ll_map.c index e9ae129..fd7db55 100644 --- a/lib/ll_map.c +++ b/lib/ll_map.c @@ -22,10 +22,11 @@ #include "libnetlink.h" #include "ll_map.h" +#include "hlist.h" -struct ll_cache -{ - struct ll_cache *idx_next; +struct ll_cache { + struct hlist_node idx_hash; + struct hlist_node name_hash; unsigned flags; int index; unsigned short type; @@ -33,49 +34,107 @@ struct ll_cache }; #define IDXMAP_SIZE 1024 -static struct ll_cache *idx_head[IDXMAP_SIZE]; +static struct hlist_head idx_head[IDXMAP_SIZE]; +static struct hlist_head name_head[IDXMAP_SIZE]; -static inline struct ll_cache *idxhead(int idx) +static struct ll_cache *ll_get_by_index(unsigned index) { - return idx_head[idx & (IDXMAP_SIZE - 1)]; + struct hlist_node *n; + unsigned h = index & (IDXMAP_SIZE - 1); + + hlist_for_each(n, &idx_head[h]) { + struct ll_cache *im + = container_of(n, struct ll_cache, idx_hash); + if (im->index == index) + return im; + } + + return NULL; +} + +static unsigned namehash(const char *str) +{ + unsigned hash = 5381; + + while (*str) + hash = ((hash << 5) + hash) + *str++; /* hash * 33 + c */ + + return hash; +} + +static struct ll_cache *ll_get_by_name(const char *name) +{ + struct hlist_node *n; + unsigned h = namehash(name) & (IDXMAP_SIZE - 1); + + hlist_for_each(n, &name_head[h]) { + struct ll_cache *im + = container_of(n, struct ll_cache, name_hash); + + if (strncmp(im->name, name, IFNAMSIZ) == 0) + return im; + } + + return NULL; } int ll_remember_index(const struct sockaddr_nl *who, struct nlmsghdr *n, void *arg) { - int h; + unsigned int h; + const char *ifname; struct ifinfomsg *ifi = NLMSG_DATA(n); - struct ll_cache *im, **imp; + struct ll_cache *im; struct rtattr *tb[IFLA_MAX+1]; - if (n->nlmsg_type != RTM_NEWLINK) + if (n->nlmsg_type != RTM_NEWLINK && n->nlmsg_type != RTM_DELLINK) return 0; if (n->nlmsg_len < NLMSG_LENGTH(sizeof(ifi))) return -1; + im = ll_get_by_index(ifi->ifi_index); + if (n->nlmsg_type == RTM_DELLINK) { + if (im) { + hlist_del(&im->name_hash); + hlist_del(&im->idx_hash); + free(im); + } + return 0; + } + memset(tb, 0, sizeof(tb)); parse_rtattr(tb, IFLA_MAX, IFLA_RTA(ifi), IFLA_PAYLOAD(n)); - if (tb[IFLA_IFNAME] == NULL) + ifname = rta_getattr_str(tb[IFLA_IFNAME]); + if (ifname == NULL) return 0; - h = ifi->ifi_index & (IDXMAP_SIZE - 1); - for (imp = &idx_head[h]; (im=*imp)!=NULL; imp = &im->idx_next) - if (im->index == ifi->ifi_index) - break; - - if (im == NULL) { - im = malloc(sizeof(*im)); - if (im == NULL) - return 0; - im->idx_next = *imp; - im->index = ifi->ifi_index; - *imp = im; + if (im) { + /* change to existing entry */ + if (strcmp(im->name, ifname) != 0) { + hlist_del(&im->name_hash); + h = namehash(ifname) & (IDXMAP_SIZE - 1); + hlist_add_head(&im->name_hash, &name_head[h]); + } + + im->flags = ifi->ifi_flags; + return 0; } + im = malloc(sizeof(*im)); + if (im == NULL) + return 0; + im->index = ifi->ifi_index; + strcpy(im->name, ifname); im->type = ifi->ifi_type; im->flags = ifi->ifi_flags; - strcpy(im->name, RTA_DATA(tb[IFLA_IFNAME])); + + h = ifi->ifi_index & (IDXMAP_SIZE - 1); + hlist_add_head(&im->idx_hash, &idx_head[h]); + + h = namehash(ifname) & (IDXMAP_SIZE - 1); + hlist_add_head(&im->name_hash, &name_head[h]); + return 0; } @@ -86,15 +145,16 @@ const char *ll_idx_n2a(unsigned idx, char *buf) if (idx == 0) return "*"; - for (im = idxhead(idx); im; im = im->idx_next) - if (im->index == idx) - return im->name; + im = ll_get_by_index(idx); + if (im) + return im->name; + + if (if_indextoname(idx, buf) == NULL) + snprintf(buf, IFNAMSIZ, "if%d", idx); - snprintf(buf, IFNAMSIZ, "if%d", idx); return buf; } - const char *ll_index_to_name(unsigned idx) { static char nbuf[IFNAMSIZ]; @@ -108,10 +168,9 @@ int ll_index_to_type(unsigned idx) if (idx == 0) return -1; - for (im = idxhead(idx); im; im = im->idx_next) - if (im->index == idx) - return im->type; - return -1; + + im = ll_get_by_index(idx); + return im ? im->type : -1; } unsigned ll_index_to_flags(unsigned idx) @@ -121,35 +180,21 @@ unsigned ll_index_to_flags(unsigned idx) if (idx == 0) return 0; - for (im = idxhead(idx); im; im = im->idx_next) - if (im->index == idx) - return im->flags; - return 0; + im = ll_get_by_index(idx); + return im ? im->flags : -1; } unsigned ll_name_to_index(const char *name) { - static char ncache[IFNAMSIZ]; - static int icache; - struct ll_cache *im; - int i; + const struct ll_cache *im; unsigned idx; if (name == NULL) return 0; - if (icache && strcmp(name, ncache) == 0) - return icache; - - for (i=0; iidx_next) { - if (strcmp(im->name, name) == 0) { - icache = im->index; - strcpy(ncache, name); - return im->index; - } - } - } + im = ll_get_by_name(name); + if (im) + return im->index; idx = if_nametoindex(name); if (idx == 0) @@ -157,12 +202,12 @@ unsigned ll_name_to_index(const char *name) return idx; } -int ll_init_map(struct rtnl_handle *rth) +void ll_init_map(struct rtnl_handle *rth) { static int initialized; if (initialized) - return 0; + return; if (rtnl_wilddump_request(rth, AF_UNSPEC, RTM_GETLINK) < 0) { perror("Cannot send dump request"); @@ -175,6 +220,4 @@ int ll_init_map(struct rtnl_handle *rth) } initialized = 1; - - return 0; } -- 1.7.10.4