From owner-freebsd-net@FreeBSD.ORG Tue Feb 26 16:56:43 2013 Return-Path: Delivered-To: freebsd-net@freebsd.org Received: from mx1.freebsd.org (mx1.FreeBSD.org [8.8.178.115]) by hub.freebsd.org (Postfix) with ESMTP id C2E71E94 for ; Tue, 26 Feb 2013 16:56:43 +0000 (UTC) (envelope-from dkandula@gmail.com) Received: from mail-wg0-f49.google.com (mail-wg0-f49.google.com [74.125.82.49]) by mx1.freebsd.org (Postfix) with ESMTP id 4BEC0FB4 for ; Tue, 26 Feb 2013 16:56:42 +0000 (UTC) Received: by mail-wg0-f49.google.com with SMTP id 15so3508507wgd.4 for ; Tue, 26 Feb 2013 08:56:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:date:message-id:subject:from:to :content-type; bh=r2s96hN4XTxXqEV0nnh62fivMJnlO3r7XjP/kkgibq8=; b=pnSyNvLLMGiIP4gfYGBDt7i76xBU3+d0JvheRTJznqujDm7HuMRuabzUTChUiQdtbo apT+hI8DRW4aWKjXEQmByb3xrDgNLAh24OQJpxZuDnJBpUjTQ5EmBPU30HuxYSt9Ahl3 feOKA0uW8tsHUInqF86SlDUa00KNjtHf4hgbP8Wbwu2HYVVg5RfGHADC/M6oufkZURWA /0mn+j3vObXw+ZZvdRcYBeWs38YkX95C/chpEIe3dUFUggzBc3xjG39ct6OLq7gRYLaS SNi3miScEC/wm+mGN822spFcYRFsrD0fu3Lk1AVxMPgTyA2Ow6Dd0k+2wQ4A7BQNGc9i Eviw== MIME-Version: 1.0 X-Received: by 10.194.108.229 with SMTP id hn5mr28045882wjb.8.1361897801968; Tue, 26 Feb 2013 08:56:41 -0800 (PST) Received: by 10.194.108.104 with HTTP; Tue, 26 Feb 2013 08:56:41 -0800 (PST) Date: Tue, 26 Feb 2013 11:56:41 -0500 Message-ID: Subject: Clarifications required in rn_delete From: Dheeraj Kandula To: freebsd-net@freebsd.org Content-Type: text/plain; charset=ISO-8859-1 X-Content-Filtered-By: Mailman/MimeDel 2.1.14 X-BeenThere: freebsd-net@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Networking and TCP/IP with FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 26 Feb 2013 16:56:43 -0000 Hey All, I have been reading through the routing path code in FreeBSD 9.1 and have a few questions while adding and deleting a route using rn_addroute() and rn_delete(). My questions are highlighted in bold. In the code fragment below - part of rn_delete() function: b = -1 - tt->rn_bit; t = saved_tt->rn_parent; if (b > t->rn_bit) goto on1; /* Wasn't lifted at all */ do { x = t; t = t->rn_parent; } while (b <= t->rn_bit && x != top); for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) if (m == saved_m) { *mp = m->rm_mklist; MKFree(m); break; } if (m == 0) { log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); if (tt->rn_flags & RNF_NORMAL) return (0); /* Dangling ref to us */ } the node "m" inside the for loop is removed from x's rn_mklist and inserted into rn_mkfreelist. *Shouldn't a test for the rm_refs similar to code below - part of rn_delete() too - be performed.??* /* * Demote routes attached to us. */ if (t->rn_mklist) { if (x->rn_bit >= 0) { for (mp = &x->rn_mklist; (m = *mp);) mp = &m->rm_mklist; *mp = t->rn_mklist; } else { /* If there are any key,mask pairs in a sibling duped-key chain, some subset will appear sorted in the same order attached to our mklist */ for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) if (m == x->rn_mklist) { struct radix_mask *mm = m->rm_mklist; x->rn_mklist = 0; * if (--(m->rm_refs) < 0) MKFree(m);* m = mm; } if (m) log(LOG_ERR, "rn_delete: Orphaned Mask %p at %p\n", m, x); } } My understanding is that for leaf nodes that represent a network route, there will be only one radix_mask node in the linked list. When a new route is being added i.e. rn_addroute(), the other child of the new route's parent i.e. the sibling of the new route's node, can be either a leaf or an internal node. The scenarios are described below: 1. Leaf Node. a. If it is a leaf that is a network route and no duplicate routes at x i.e. x->rn_dupedkey is NULL, a new radix_mask node is created when the rn_bit is >= the new route's rn_bit i.e. x->rn_bit >= b_leaf and x->rn_mklist == 0. /* Promote general routes from below */ if (x->rn_bit < 0) { for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { *mp = m = rn_new_radix_mask(x, 0); if (m) mp = &m->rm_mklist; } } b. If it is a leaf that is a network node and there are duplicate routes at x i.e. x->rn_dupedkey is NON-NULL, a new radix_mask node is added for every node in the duplicate linked list if. x->rn_bit >= b_leaf. as per the code above in case a. 2. Internal Node: If it is an internal node and the x->rn_mklist is NON-NULL, the linked list headed by x->rn_mklist is traversed and the traversal is discontinued only if m->rm_bit >= b_leaf. else if (x->rn_mklist) { /* * Skip over masks whose index is > that of new node */ for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) if (m->rm_bit >= b_leaf) break; t->rn_mklist = m; *mp = 0; } Here x will always be an internal node and hence if (m->rm_bit >= b_leaf) will always fail as b_leaf is a signed short and rm_bit is a signed short too and b_leaf is negative as b_leaf is -1 -t->rn_bit. *Isn't it? Is this a bug in the code.* Dheeraj