net/decnet/dn_table.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * DECnet       An implementation of the DECnet protocol suite for the LINUX
0004  *              operating system.  DECnet is implemented using the  BSD Socket
0005  *              interface as the means of communication with the user level.
0006  *
0007  *              DECnet Routing Forwarding Information Base (Routing Tables)
0008  *
0009  * Author:      Steve Whitehouse <SteveW@ACM.org>
0010  *              Mostly copied from the IPv4 routing code
0011  *
0012  *
0013  * Changes:
0014  *
0015  */
0016 #include <linux/string.h>
0017 #include <linux/net.h>
0018 #include <linux/socket.h>
0019 #include <linux/slab.h>
0020 #include <linux/sockios.h>
0021 #include <linux/init.h>
0022 #include <linux/skbuff.h>
0023 #include <linux/rtnetlink.h>
0024 #include <linux/proc_fs.h>
0025 #include <linux/netdevice.h>
0026 #include <linux/timer.h>
0027 #include <linux/spinlock.h>
0028 #include <linux/atomic.h>
0029 #include <linux/uaccess.h>
0030 #include <linux/route.h> /* RTF_xxx */
0031 #include <net/neighbour.h>
0032 #include <net/netlink.h>
0033 #include <net/tcp.h>
0034 #include <net/dst.h>
0035 #include <net/flow.h>
0036 #include <net/fib_rules.h>
0037 #include <net/dn.h>
0038 #include <net/dn_route.h>
0039 #include <net/dn_fib.h>
0040 #include <net/dn_neigh.h>
0041 #include <net/dn_dev.h>
0042
0043 struct dn_zone
0044 {
0045     struct dn_zone      *dz_next;
0046     struct dn_fib_node  **dz_hash;
0047     int         dz_nent;
0048     int         dz_divisor;
0049     u32         dz_hashmask;
0050 #define DZ_HASHMASK(dz) ((dz)->dz_hashmask)
0051     int         dz_order;
0052     __le16          dz_mask;
0053 #define DZ_MASK(dz) ((dz)->dz_mask)
0054 };
0055
0056 struct dn_hash
0057 {
0058     struct dn_zone  *dh_zones[17];
0059     struct dn_zone  *dh_zone_list;
0060 };
0061
0062 #define dz_key_0(key)       ((key).datum = 0)
0063
0064 #define for_nexthops(fi) { int nhsel; const struct dn_fib_nh *nh;\
0065     for(nhsel = 0, nh = (fi)->fib_nh; nhsel < (fi)->fib_nhs; nh++, nhsel++)
0066
0067 #define endfor_nexthops(fi) }
0068
0069 #define DN_MAX_DIVISOR 1024
0070 #define DN_S_ZOMBIE 1
0071 #define DN_S_ACCESSED 2
0072
0073 #define DN_FIB_SCAN(f, fp) \
0074 for( ; ((f) = *(fp)) != NULL; (fp) = &(f)->fn_next)
0075
0076 #define DN_FIB_SCAN_KEY(f, fp, key) \
0077 for( ; ((f) = *(fp)) != NULL && dn_key_eq((f)->fn_key, (key)); (fp) = &(f)->fn_next)
0078
0079 #define RT_TABLE_MIN 1
0080 #define DN_FIB_TABLE_HASHSZ 256
0081 static struct hlist_head dn_fib_table_hash[DN_FIB_TABLE_HASHSZ];
0082 static DEFINE_RWLOCK(dn_fib_tables_lock);
0083
0084 static struct kmem_cache *dn_hash_kmem __read_mostly;
0085 static int dn_fib_hash_zombies;
0086
0087 static inline dn_fib_idx_t dn_hash(dn_fib_key_t key, struct dn_zone *dz)
0088 {
0089     u16 h = le16_to_cpu(key.datum)>>(16 - dz->dz_order);
0090     h ^= (h >> 10);
0091     h ^= (h >> 6);
0092     h &= DZ_HASHMASK(dz);
0093     return *(dn_fib_idx_t *)&h;
0094 }
0095
0096 static inline dn_fib_key_t dz_key(__le16 dst, struct dn_zone *dz)
0097 {
0098     dn_fib_key_t k;
0099     k.datum = dst & DZ_MASK(dz);
0100     return k;
0101 }
0102
0103 static inline struct dn_fib_node **dn_chain_p(dn_fib_key_t key, struct dn_zone *dz)
0104 {
0105     return &dz->dz_hash[dn_hash(key, dz).datum];
0106 }
0107
0108 static inline struct dn_fib_node *dz_chain(dn_fib_key_t key, struct dn_zone *dz)
0109 {
0110     return dz->dz_hash[dn_hash(key, dz).datum];
0111 }
0112
0113 static inline int dn_key_eq(dn_fib_key_t a, dn_fib_key_t b)
0114 {
0115     return a.datum == b.datum;
0116 }
0117
0118 static inline int dn_key_leq(dn_fib_key_t a, dn_fib_key_t b)
0119 {
0120     return a.datum <= b.datum;
0121 }
0122
0123 static inline void dn_rebuild_zone(struct dn_zone *dz,
0124                    struct dn_fib_node **old_ht,
0125                    int old_divisor)
0126 {
0127     struct dn_fib_node *f, **fp, *next;
0128     int i;
0129
0130     for(i = 0; i < old_divisor; i++) {
0131         for(f = old_ht[i]; f; f = next) {
0132             next = f->fn_next;
0133             for(fp = dn_chain_p(f->fn_key, dz);
0134                 *fp && dn_key_leq((*fp)->fn_key, f->fn_key);
0135                 fp = &(*fp)->fn_next)
0136                 /* NOTHING */;
0137             f->fn_next = *fp;
0138             *fp = f;
0139         }
0140     }
0141 }
0142
0143 static void dn_rehash_zone(struct dn_zone *dz)
0144 {
0145     struct dn_fib_node **ht, **old_ht;
0146     int old_divisor, new_divisor;
0147     u32 new_hashmask;
0148
0149     old_divisor = dz->dz_divisor;
0150
0151     switch (old_divisor) {
0152     case 16:
0153         new_divisor = 256;
0154         new_hashmask = 0xFF;
0155         break;
0156     default:
0157         printk(KERN_DEBUG "DECnet: dn_rehash_zone: BUG! %d\n",
0158                old_divisor);
0159         fallthrough;
0160     case 256:
0161         new_divisor = 1024;
0162         new_hashmask = 0x3FF;
0163         break;
0164     }
0165
0166     ht = kcalloc(new_divisor, sizeof(struct dn_fib_node*), GFP_KERNEL);
0167     if (ht == NULL)
0168         return;
0169
0170     write_lock_bh(&dn_fib_tables_lock);
0171     old_ht = dz->dz_hash;
0172     dz->dz_hash = ht;
0173     dz->dz_hashmask = new_hashmask;
0174     dz->dz_divisor = new_divisor;
0175     dn_rebuild_zone(dz, old_ht, old_divisor);
0176     write_unlock_bh(&dn_fib_tables_lock);
0177     kfree(old_ht);
0178 }
0179
0180 static void dn_free_node(struct dn_fib_node *f)
0181 {
0182     dn_fib_release_info(DN_FIB_INFO(f));
0183     kmem_cache_free(dn_hash_kmem, f);
0184 }
0185
0186
0187 static struct dn_zone *dn_new_zone(struct dn_hash *table, int z)
0188 {
0189     int i;
0190     struct dn_zone *dz = kzalloc(sizeof(struct dn_zone), GFP_KERNEL);
0191     if (!dz)
0192         return NULL;
0193
0194     if (z) {
0195         dz->dz_divisor = 16;
0196         dz->dz_hashmask = 0x0F;
0197     } else {
0198         dz->dz_divisor = 1;
0199         dz->dz_hashmask = 0;
0200     }
0201
0202     dz->dz_hash = kcalloc(dz->dz_divisor, sizeof(struct dn_fib_node *), GFP_KERNEL);
0203     if (!dz->dz_hash) {
0204         kfree(dz);
0205         return NULL;
0206     }
0207
0208     dz->dz_order = z;
0209     dz->dz_mask = dnet_make_mask(z);
0210
0211     for(i = z + 1; i <= 16; i++)
0212         if (table->dh_zones[i])
0213             break;
0214
0215     write_lock_bh(&dn_fib_tables_lock);
0216     if (i>16) {
0217         dz->dz_next = table->dh_zone_list;
0218         table->dh_zone_list = dz;
0219     } else {
0220         dz->dz_next = table->dh_zones[i]->dz_next;
0221         table->dh_zones[i]->dz_next = dz;
0222     }
0223     table->dh_zones[z] = dz;
0224     write_unlock_bh(&dn_fib_tables_lock);
0225     return dz;
0226 }
0227
0228
0229 static int dn_fib_nh_match(struct rtmsg *r, struct nlmsghdr *nlh, struct nlattr *attrs[], struct dn_fib_info *fi)
0230 {
0231     struct rtnexthop *nhp;
0232     int nhlen;
0233
0234     if (attrs[RTA_PRIORITY] &&
0235         nla_get_u32(attrs[RTA_PRIORITY]) != fi->fib_priority)
0236         return 1;
0237
0238     if (attrs[RTA_OIF] || attrs[RTA_GATEWAY]) {
0239         if ((!attrs[RTA_OIF] || nla_get_u32(attrs[RTA_OIF]) == fi->fib_nh->nh_oif) &&
0240             (!attrs[RTA_GATEWAY]  || nla_get_le16(attrs[RTA_GATEWAY]) != fi->fib_nh->nh_gw))
0241             return 0;
0242         return 1;
0243     }
0244
0245     if (!attrs[RTA_MULTIPATH])
0246         return 0;
0247
0248     nhp = nla_data(attrs[RTA_MULTIPATH]);
0249     nhlen = nla_len(attrs[RTA_MULTIPATH]);
0250
0251     for_nexthops(fi) {
0252         int attrlen = nhlen - sizeof(struct rtnexthop);
0253         __le16 gw;
0254
0255         if (attrlen < 0 || (nhlen -= nhp->rtnh_len) < 0)
0256             return -EINVAL;
0257         if (nhp->rtnh_ifindex && nhp->rtnh_ifindex != nh->nh_oif)
0258             return 1;
0259         if (attrlen) {
0260             struct nlattr *gw_attr;
0261
0262             gw_attr = nla_find((struct nlattr *) (nhp + 1), attrlen, RTA_GATEWAY);
0263             gw = gw_attr ? nla_get_le16(gw_attr) : 0;
0264
0265             if (gw && gw != nh->nh_gw)
0266                 return 1;
0267         }
0268         nhp = RTNH_NEXT(nhp);
0269     } endfor_nexthops(fi);
0270
0271     return 0;
0272 }
0273
0274 static inline size_t dn_fib_nlmsg_size(struct dn_fib_info *fi)
0275 {
0276     size_t payload = NLMSG_ALIGN(sizeof(struct rtmsg))
0277              + nla_total_size(4) /* RTA_TABLE */
0278              + nla_total_size(2) /* RTA_DST */
0279              + nla_total_size(4) /* RTA_PRIORITY */
0280              + nla_total_size(TCP_CA_NAME_MAX); /* RTAX_CC_ALGO */
0281
0282     /* space for nested metrics */
0283     payload += nla_total_size((RTAX_MAX * nla_total_size(4)));
0284
0285     if (fi->fib_nhs) {
0286         /* Also handles the special case fib_nhs == 1 */
0287
0288         /* each nexthop is packed in an attribute */
0289         size_t nhsize = nla_total_size(sizeof(struct rtnexthop));
0290
0291         /* may contain a gateway attribute */
0292         nhsize += nla_total_size(4);
0293
0294         /* all nexthops are packed in a nested attribute */
0295         payload += nla_total_size(fi->fib_nhs * nhsize);
0296     }
0297
0298     return payload;
0299 }
0300
0301 static int dn_fib_dump_info(struct sk_buff *skb, u32 portid, u32 seq, int event,
0302             u32 tb_id, u8 type, u8 scope, void *dst, int dst_len,
0303             struct dn_fib_info *fi, unsigned int flags)
0304 {
0305     struct rtmsg *rtm;
0306     struct nlmsghdr *nlh;
0307
0308     nlh = nlmsg_put(skb, portid, seq, event, sizeof(*rtm), flags);
0309     if (!nlh)
0310         return -EMSGSIZE;
0311
0312     rtm = nlmsg_data(nlh);
0313     rtm->rtm_family = AF_DECnet;
0314     rtm->rtm_dst_len = dst_len;
0315     rtm->rtm_src_len = 0;
0316     rtm->rtm_tos = 0;
0317     rtm->rtm_table = tb_id;
0318     rtm->rtm_flags = fi->fib_flags;
0319     rtm->rtm_scope = scope;
0320     rtm->rtm_type  = type;
0321     rtm->rtm_protocol = fi->fib_protocol;
0322
0323     if (nla_put_u32(skb, RTA_TABLE, tb_id) < 0)
0324         goto errout;
0325
0326     if (rtm->rtm_dst_len &&
0327         nla_put(skb, RTA_DST, 2, dst) < 0)
0328         goto errout;
0329
0330     if (fi->fib_priority &&
0331         nla_put_u32(skb, RTA_PRIORITY, fi->fib_priority) < 0)
0332         goto errout;
0333
0334     if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0)
0335         goto errout;
0336
0337     if (fi->fib_nhs == 1) {
0338         if (fi->fib_nh->nh_gw &&
0339             nla_put_le16(skb, RTA_GATEWAY, fi->fib_nh->nh_gw) < 0)
0340             goto errout;
0341
0342         if (fi->fib_nh->nh_oif &&
0343             nla_put_u32(skb, RTA_OIF, fi->fib_nh->nh_oif) < 0)
0344             goto errout;
0345     }
0346
0347     if (fi->fib_nhs > 1) {
0348         struct rtnexthop *nhp;
0349         struct nlattr *mp_head;
0350
0351         mp_head = nla_nest_start_noflag(skb, RTA_MULTIPATH);
0352         if (!mp_head)
0353             goto errout;
0354
0355         for_nexthops(fi) {
0356             if (!(nhp = nla_reserve_nohdr(skb, sizeof(*nhp))))
0357                 goto errout;
0358
0359             nhp->rtnh_flags = nh->nh_flags & 0xFF;
0360             nhp->rtnh_hops = nh->nh_weight - 1;
0361             nhp->rtnh_ifindex = nh->nh_oif;
0362
0363             if (nh->nh_gw &&
0364                 nla_put_le16(skb, RTA_GATEWAY, nh->nh_gw) < 0)
0365                 goto errout;
0366
0367             nhp->rtnh_len = skb_tail_pointer(skb) - (unsigned char *)nhp;
0368         } endfor_nexthops(fi);
0369
0370         nla_nest_end(skb, mp_head);
0371     }
0372
0373     nlmsg_end(skb, nlh);
0374     return 0;
0375
0376 errout:
0377     nlmsg_cancel(skb, nlh);
0378     return -EMSGSIZE;
0379 }
0380
0381
0382 static void dn_rtmsg_fib(int event, struct dn_fib_node *f, int z, u32 tb_id,
0383             struct nlmsghdr *nlh, struct netlink_skb_parms *req)
0384 {
0385     struct sk_buff *skb;
0386     u32 portid = req ? req->portid : 0;
0387     int err = -ENOBUFS;
0388
0389     skb = nlmsg_new(dn_fib_nlmsg_size(DN_FIB_INFO(f)), GFP_KERNEL);
0390     if (skb == NULL)
0391         goto errout;
0392
0393     err = dn_fib_dump_info(skb, portid, nlh->nlmsg_seq, event, tb_id,
0394                    f->fn_type, f->fn_scope, &f->fn_key, z,
0395                    DN_FIB_INFO(f), 0);
0396     if (err < 0) {
0397         /* -EMSGSIZE implies BUG in dn_fib_nlmsg_size() */
0398         WARN_ON(err == -EMSGSIZE);
0399         kfree_skb(skb);
0400         goto errout;
0401     }
0402     rtnl_notify(skb, &init_net, portid, RTNLGRP_DECnet_ROUTE, nlh, GFP_KERNEL);
0403     return;
0404 errout:
0405     if (err < 0)
0406         rtnl_set_sk_err(&init_net, RTNLGRP_DECnet_ROUTE, err);
0407 }
0408
0409 static __inline__ int dn_hash_dump_bucket(struct sk_buff *skb,
0410                 struct netlink_callback *cb,
0411                 struct dn_fib_table *tb,
0412                 struct dn_zone *dz,
0413                 struct dn_fib_node *f)
0414 {
0415     int i, s_i;
0416
0417     s_i = cb->args[4];
0418     for(i = 0; f; i++, f = f->fn_next) {
0419         if (i < s_i)
0420             continue;
0421         if (f->fn_state & DN_S_ZOMBIE)
0422             continue;
0423         if (dn_fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
0424                 cb->nlh->nlmsg_seq,
0425                 RTM_NEWROUTE,
0426                 tb->n,
0427                 (f->fn_state & DN_S_ZOMBIE) ? 0 : f->fn_type,
0428                 f->fn_scope, &f->fn_key, dz->dz_order,
0429                 f->fn_info, NLM_F_MULTI) < 0) {
0430             cb->args[4] = i;
0431             return -1;
0432         }
0433     }
0434     cb->args[4] = i;
0435     return skb->len;
0436 }
0437
0438 static __inline__ int dn_hash_dump_zone(struct sk_buff *skb,
0439                 struct netlink_callback *cb,
0440                 struct dn_fib_table *tb,
0441                 struct dn_zone *dz)
0442 {
0443     int h, s_h;
0444
0445     s_h = cb->args[3];
0446     for(h = 0; h < dz->dz_divisor; h++) {
0447         if (h < s_h)
0448             continue;
0449         if (h > s_h)
0450             memset(&cb->args[4], 0, sizeof(cb->args) - 4*sizeof(cb->args[0]));
0451         if (dz->dz_hash == NULL || dz->dz_hash[h] == NULL)
0452             continue;
0453         if (dn_hash_dump_bucket(skb, cb, tb, dz, dz->dz_hash[h]) < 0) {
0454             cb->args[3] = h;
0455             return -1;
0456         }
0457     }
0458     cb->args[3] = h;
0459     return skb->len;
0460 }
0461
0462 static int dn_fib_table_dump(struct dn_fib_table *tb, struct sk_buff *skb,
0463                 struct netlink_callback *cb)
0464 {
0465     int m, s_m;
0466     struct dn_zone *dz;
0467     struct dn_hash *table = (struct dn_hash *)tb->data;
0468
0469     s_m = cb->args[2];
0470     read_lock(&dn_fib_tables_lock);
0471     for(dz = table->dh_zone_list, m = 0; dz; dz = dz->dz_next, m++) {
0472         if (m < s_m)
0473             continue;
0474         if (m > s_m)
0475             memset(&cb->args[3], 0, sizeof(cb->args) - 3*sizeof(cb->args[0]));
0476
0477         if (dn_hash_dump_zone(skb, cb, tb, dz) < 0) {
0478             cb->args[2] = m;
0479             read_unlock(&dn_fib_tables_lock);
0480             return -1;
0481         }
0482     }
0483     read_unlock(&dn_fib_tables_lock);
0484     cb->args[2] = m;
0485
0486     return skb->len;
0487 }
0488
0489 int dn_fib_dump(struct sk_buff *skb, struct netlink_callback *cb)
0490 {
0491     struct net *net = sock_net(skb->sk);
0492     unsigned int h, s_h;
0493     unsigned int e = 0, s_e;
0494     struct dn_fib_table *tb;
0495     int dumped = 0;
0496
0497     if (!net_eq(net, &init_net))
0498         return 0;
0499
0500     if (nlmsg_len(cb->nlh) >= sizeof(struct rtmsg) &&
0501         ((struct rtmsg *)nlmsg_data(cb->nlh))->rtm_flags&RTM_F_CLONED)
0502             return dn_cache_dump(skb, cb);
0503
0504     s_h = cb->args[0];
0505     s_e = cb->args[1];
0506
0507     for (h = s_h; h < DN_FIB_TABLE_HASHSZ; h++, s_h = 0) {
0508         e = 0;
0509         hlist_for_each_entry(tb, &dn_fib_table_hash[h], hlist) {
0510             if (e < s_e)
0511                 goto next;
0512             if (dumped)
0513                 memset(&cb->args[2], 0, sizeof(cb->args) -
0514                          2 * sizeof(cb->args[0]));
0515             if (tb->dump(tb, skb, cb) < 0)
0516                 goto out;
0517             dumped = 1;
0518 next:
0519             e++;
0520         }
0521     }
0522 out:
0523     cb->args[1] = e;
0524     cb->args[0] = h;
0525
0526     return skb->len;
0527 }
0528
0529 static int dn_fib_table_insert(struct dn_fib_table *tb, struct rtmsg *r, struct nlattr *attrs[],
0530                    struct nlmsghdr *n, struct netlink_skb_parms *req)
0531 {
0532     struct dn_hash *table = (struct dn_hash *)tb->data;
0533     struct dn_fib_node *new_f, *f, **fp, **del_fp;
0534     struct dn_zone *dz;
0535     struct dn_fib_info *fi;
0536     int z = r->rtm_dst_len;
0537     int type = r->rtm_type;
0538     dn_fib_key_t key;
0539     int err;
0540
0541     if (z > 16)
0542         return -EINVAL;
0543
0544     dz = table->dh_zones[z];
0545     if (!dz && !(dz = dn_new_zone(table, z)))
0546         return -ENOBUFS;
0547
0548     dz_key_0(key);
0549     if (attrs[RTA_DST]) {
0550         __le16 dst = nla_get_le16(attrs[RTA_DST]);
0551         if (dst & ~DZ_MASK(dz))
0552             return -EINVAL;
0553         key = dz_key(dst, dz);
0554     }
0555
0556     if ((fi = dn_fib_create_info(r, attrs, n, &err)) == NULL)
0557         return err;
0558
0559     if (dz->dz_nent > (dz->dz_divisor << 2) &&
0560             dz->dz_divisor > DN_MAX_DIVISOR &&
0561             (z==16 || (1<<z) > dz->dz_divisor))
0562         dn_rehash_zone(dz);
0563
0564     fp = dn_chain_p(key, dz);
0565
0566     DN_FIB_SCAN(f, fp) {
0567         if (dn_key_leq(key, f->fn_key))
0568             break;
0569     }
0570
0571     del_fp = NULL;
0572
0573     if (f && (f->fn_state & DN_S_ZOMBIE) &&
0574             dn_key_eq(f->fn_key, key)) {
0575         del_fp = fp;
0576         fp = &f->fn_next;
0577         f = *fp;
0578         goto create;
0579     }
0580
0581     DN_FIB_SCAN_KEY(f, fp, key) {
0582         if (fi->fib_priority <= DN_FIB_INFO(f)->fib_priority)
0583             break;
0584     }
0585
0586     if (f && dn_key_eq(f->fn_key, key) &&
0587             fi->fib_priority == DN_FIB_INFO(f)->fib_priority) {
0588         struct dn_fib_node **ins_fp;
0589
0590         err = -EEXIST;
0591         if (n->nlmsg_flags & NLM_F_EXCL)
0592             goto out;
0593
0594         if (n->nlmsg_flags & NLM_F_REPLACE) {
0595             del_fp = fp;
0596             fp = &f->fn_next;
0597             f = *fp;
0598             goto replace;
0599         }
0600
0601         ins_fp = fp;
0602         err = -EEXIST;
0603
0604         DN_FIB_SCAN_KEY(f, fp, key) {
0605             if (fi->fib_priority != DN_FIB_INFO(f)->fib_priority)
0606                 break;
0607             if (f->fn_type == type &&
0608                 f->fn_scope == r->rtm_scope &&
0609                 DN_FIB_INFO(f) == fi)
0610                 goto out;
0611         }
0612
0613         if (!(n->nlmsg_flags & NLM_F_APPEND)) {
0614             fp = ins_fp;
0615             f = *fp;
0616         }
0617     }
0618
0619 create:
0620     err = -ENOENT;
0621     if (!(n->nlmsg_flags & NLM_F_CREATE))
0622         goto out;
0623
0624 replace:
0625     err = -ENOBUFS;
0626     new_f = kmem_cache_zalloc(dn_hash_kmem, GFP_KERNEL);
0627     if (new_f == NULL)
0628         goto out;
0629
0630     new_f->fn_key = key;
0631     new_f->fn_type = type;
0632     new_f->fn_scope = r->rtm_scope;
0633     DN_FIB_INFO(new_f) = fi;
0634
0635     new_f->fn_next = f;
0636     write_lock_bh(&dn_fib_tables_lock);
0637     *fp = new_f;
0638     write_unlock_bh(&dn_fib_tables_lock);
0639     dz->dz_nent++;
0640
0641     if (del_fp) {
0642         f = *del_fp;
0643         write_lock_bh(&dn_fib_tables_lock);
0644         *del_fp = f->fn_next;
0645         write_unlock_bh(&dn_fib_tables_lock);
0646
0647         if (!(f->fn_state & DN_S_ZOMBIE))
0648             dn_rtmsg_fib(RTM_DELROUTE, f, z, tb->n, n, req);
0649         if (f->fn_state & DN_S_ACCESSED)
0650             dn_rt_cache_flush(-1);
0651         dn_free_node(f);
0652         dz->dz_nent--;
0653     } else {
0654         dn_rt_cache_flush(-1);
0655     }
0656
0657     dn_rtmsg_fib(RTM_NEWROUTE, new_f, z, tb->n, n, req);
0658
0659     return 0;
0660 out:
0661     dn_fib_release_info(fi);
0662     return err;
0663 }
0664
0665
0666 static int dn_fib_table_delete(struct dn_fib_table *tb, struct rtmsg *r, struct nlattr *attrs[],
0667                    struct nlmsghdr *n, struct netlink_skb_parms *req)
0668 {
0669     struct dn_hash *table = (struct dn_hash*)tb->data;
0670     struct dn_fib_node **fp, **del_fp, *f;
0671     int z = r->rtm_dst_len;
0672     struct dn_zone *dz;
0673     dn_fib_key_t key;
0674     int matched;
0675
0676
0677     if (z > 16)
0678         return -EINVAL;
0679
0680     if ((dz = table->dh_zones[z]) == NULL)
0681         return -ESRCH;
0682
0683     dz_key_0(key);
0684     if (attrs[RTA_DST]) {
0685         __le16 dst = nla_get_le16(attrs[RTA_DST]);
0686         if (dst & ~DZ_MASK(dz))
0687             return -EINVAL;
0688         key = dz_key(dst, dz);
0689     }
0690
0691     fp = dn_chain_p(key, dz);
0692
0693     DN_FIB_SCAN(f, fp) {
0694         if (dn_key_eq(f->fn_key, key))
0695             break;
0696         if (dn_key_leq(key, f->fn_key))
0697             return -ESRCH;
0698     }
0699
0700     matched = 0;
0701     del_fp = NULL;
0702     DN_FIB_SCAN_KEY(f, fp, key) {
0703         struct dn_fib_info *fi = DN_FIB_INFO(f);
0704
0705         if (f->fn_state & DN_S_ZOMBIE)
0706             return -ESRCH;
0707
0708         matched++;
0709
0710         if (del_fp == NULL &&
0711                 (!r->rtm_type || f->fn_type == r->rtm_type) &&
0712                 (r->rtm_scope == RT_SCOPE_NOWHERE || f->fn_scope == r->rtm_scope) &&
0713                 (!r->rtm_protocol ||
0714                     fi->fib_protocol == r->rtm_protocol) &&
0715                 dn_fib_nh_match(r, n, attrs, fi) == 0)
0716             del_fp = fp;
0717     }
0718
0719     if (del_fp) {
0720         f = *del_fp;
0721         dn_rtmsg_fib(RTM_DELROUTE, f, z, tb->n, n, req);
0722
0723         if (matched != 1) {
0724             write_lock_bh(&dn_fib_tables_lock);
0725             *del_fp = f->fn_next;
0726             write_unlock_bh(&dn_fib_tables_lock);
0727
0728             if (f->fn_state & DN_S_ACCESSED)
0729                 dn_rt_cache_flush(-1);
0730             dn_free_node(f);
0731             dz->dz_nent--;
0732         } else {
0733             f->fn_state |= DN_S_ZOMBIE;
0734             if (f->fn_state & DN_S_ACCESSED) {
0735                 f->fn_state &= ~DN_S_ACCESSED;
0736                 dn_rt_cache_flush(-1);
0737             }
0738             if (++dn_fib_hash_zombies > 128)
0739                 dn_fib_flush();
0740         }
0741
0742         return 0;
0743     }
0744
0745     return -ESRCH;
0746 }
0747
0748 static inline int dn_flush_list(struct dn_fib_node **fp, int z, struct dn_hash *table)
0749 {
0750     int found = 0;
0751     struct dn_fib_node *f;
0752
0753     while((f = *fp) != NULL) {
0754         struct dn_fib_info *fi = DN_FIB_INFO(f);
0755
0756         if (fi && ((f->fn_state & DN_S_ZOMBIE) || (fi->fib_flags & RTNH_F_DEAD))) {
0757             write_lock_bh(&dn_fib_tables_lock);
0758             *fp = f->fn_next;
0759             write_unlock_bh(&dn_fib_tables_lock);
0760
0761             dn_free_node(f);
0762             found++;
0763             continue;
0764         }
0765         fp = &f->fn_next;
0766     }
0767
0768     return found;
0769 }
0770
0771 static int dn_fib_table_flush(struct dn_fib_table *tb)
0772 {
0773     struct dn_hash *table = (struct dn_hash *)tb->data;
0774     struct dn_zone *dz;
0775     int found = 0;
0776
0777     dn_fib_hash_zombies = 0;
0778     for(dz = table->dh_zone_list; dz; dz = dz->dz_next) {
0779         int i;
0780         int tmp = 0;
0781         for(i = dz->dz_divisor-1; i >= 0; i--)
0782             tmp += dn_flush_list(&dz->dz_hash[i], dz->dz_order, table);
0783         dz->dz_nent -= tmp;
0784         found += tmp;
0785     }
0786
0787     return found;
0788 }
0789
0790 static int dn_fib_table_lookup(struct dn_fib_table *tb, const struct flowidn *flp, struct dn_fib_res *res)
0791 {
0792     int err;
0793     struct dn_zone *dz;
0794     struct dn_hash *t = (struct dn_hash *)tb->data;
0795
0796     read_lock(&dn_fib_tables_lock);
0797     for(dz = t->dh_zone_list; dz; dz = dz->dz_next) {
0798         struct dn_fib_node *f;
0799         dn_fib_key_t k = dz_key(flp->daddr, dz);
0800
0801         for(f = dz_chain(k, dz); f; f = f->fn_next) {
0802             if (!dn_key_eq(k, f->fn_key)) {
0803                 if (dn_key_leq(k, f->fn_key))
0804                     break;
0805                 else
0806                     continue;
0807             }
0808
0809             f->fn_state |= DN_S_ACCESSED;
0810
0811             if (f->fn_state&DN_S_ZOMBIE)
0812                 continue;
0813
0814             if (f->fn_scope < flp->flowidn_scope)
0815                 continue;
0816
0817             err = dn_fib_semantic_match(f->fn_type, DN_FIB_INFO(f), flp, res);
0818
0819             if (err == 0) {
0820                 res->type = f->fn_type;
0821                 res->scope = f->fn_scope;
0822                 res->prefixlen = dz->dz_order;
0823                 goto out;
0824             }
0825             if (err < 0)
0826                 goto out;
0827         }
0828     }
0829     err = 1;
0830 out:
0831     read_unlock(&dn_fib_tables_lock);
0832     return err;
0833 }
0834
0835
0836 struct dn_fib_table *dn_fib_get_table(u32 n, int create)
0837 {
0838     struct dn_fib_table *t;
0839     unsigned int h;
0840
0841     if (n < RT_TABLE_MIN)
0842         return NULL;
0843
0844     if (n > RT_TABLE_MAX)
0845         return NULL;
0846
0847     h = n & (DN_FIB_TABLE_HASHSZ - 1);
0848     rcu_read_lock();
0849     hlist_for_each_entry_rcu(t, &dn_fib_table_hash[h], hlist) {
0850         if (t->n == n) {
0851             rcu_read_unlock();
0852             return t;
0853         }
0854     }
0855     rcu_read_unlock();
0856
0857     if (!create)
0858         return NULL;
0859
0860     if (in_interrupt()) {
0861         net_dbg_ratelimited("DECnet: BUG! Attempt to create routing table from interrupt\n");
0862         return NULL;
0863     }
0864
0865     t = kzalloc(sizeof(struct dn_fib_table) + sizeof(struct dn_hash),
0866             GFP_KERNEL);
0867     if (t == NULL)
0868         return NULL;
0869
0870     t->n = n;
0871     t->insert = dn_fib_table_insert;
0872     t->delete = dn_fib_table_delete;
0873     t->lookup = dn_fib_table_lookup;
0874     t->flush  = dn_fib_table_flush;
0875     t->dump = dn_fib_table_dump;
0876     hlist_add_head_rcu(&t->hlist, &dn_fib_table_hash[h]);
0877
0878     return t;
0879 }
0880
0881 struct dn_fib_table *dn_fib_empty_table(void)
0882 {
0883     u32 id;
0884
0885     for(id = RT_TABLE_MIN; id <= RT_TABLE_MAX; id++)
0886         if (dn_fib_get_table(id, 0) == NULL)
0887             return dn_fib_get_table(id, 1);
0888     return NULL;
0889 }
0890
0891 void dn_fib_flush(void)
0892 {
0893     int flushed = 0;
0894     struct dn_fib_table *tb;
0895     unsigned int h;
0896
0897     for (h = 0; h < DN_FIB_TABLE_HASHSZ; h++) {
0898         hlist_for_each_entry(tb, &dn_fib_table_hash[h], hlist)
0899             flushed += tb->flush(tb);
0900     }
0901
0902     if (flushed)
0903         dn_rt_cache_flush(-1);
0904 }
0905
0906 void __init dn_fib_table_init(void)
0907 {
0908     dn_hash_kmem = kmem_cache_create("dn_fib_info_cache",
0909                     sizeof(struct dn_fib_info),
0910                     0, SLAB_HWCACHE_ALIGN,
0911                     NULL);
0912 }
0913
0914 void __exit dn_fib_table_cleanup(void)
0915 {
0916     struct dn_fib_table *t;
0917     struct hlist_node *next;
0918     unsigned int h;
0919
0920     write_lock(&dn_fib_tables_lock);
0921     for (h = 0; h < DN_FIB_TABLE_HASHSZ; h++) {
0922         hlist_for_each_entry_safe(t, next, &dn_fib_table_hash[h],
0923                       hlist) {
0924             hlist_del(&t->hlist);
0925             kfree(t);
0926         }
0927     }
0928     write_unlock(&dn_fib_tables_lock);
0929 }