From patchwork Thu Apr 25 10:24:27 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Arnaud Charlet X-Patchwork-Id: 239465 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 5C0ED2C010E for ; Thu, 25 Apr 2013 20:24:36 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; q=dns; s=default; b=KnDxc0q7QC7oJDQI67lXtqKRyvP9yGJu4vNUKARt1s3hwAhzep JRkJBRDvWrFe7T82j8HcKMMO97sM031TbVXigA6fhcofILFHg6LeNmjrW260QEqX e21dBGkdITD7iQYQOKARWQX6OReEf0N9Jw63S9InNp2k6Eb5xrVu/tALA= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; s= default; bh=u8eQ14K/ugd9eUCO8DXzQifGtEQ=; b=YxSF8l3OcBLhK7Y/Nh9W /8qtdH8Tg0/kO5OuMWBhF//wTyVmLFwCth3PP0P2skBbJuk9wCpLW6mYu3W6o0Im E1eqEIoix+8jOq3GPvPnpggnlLzaKrLmD+k9leXO/BEoe/hNoLX1+WDmnhY1KdnU p/fyh8H47SBAL33Mq6bSyis= Received: (qmail 18162 invoked by alias); 25 Apr 2013 10:24:30 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 18152 invoked by uid 89); 25 Apr 2013 10:24:30 -0000 X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL, BAYES_00, RCVD_IN_HOSTKARMA_NO autolearn=ham version=3.3.1 Received: from rock.gnat.com (HELO rock.gnat.com) (205.232.38.15) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Thu, 25 Apr 2013 10:24:29 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id C6A442E890; Thu, 25 Apr 2013 06:24:27 -0400 (EDT) Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id bEjJogCNJrtZ; Thu, 25 Apr 2013 06:24:27 -0400 (EDT) Received: from kwai.gnat.com (kwai.gnat.com [205.232.38.4]) by rock.gnat.com (Postfix) with ESMTP id A4EDF2E7DC; Thu, 25 Apr 2013 06:24:27 -0400 (EDT) Received: by kwai.gnat.com (Postfix, from userid 4192) id 9B1D13FF09; Thu, 25 Apr 2013 06:24:27 -0400 (EDT) Date: Thu, 25 Apr 2013 06:24:27 -0400 From: Arnaud Charlet To: gcc-patches@gcc.gnu.org Cc: Matthew Heaney Subject: [Ada] No tampering check for empty container Message-ID: <20130425102427.GA4995@adacore.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) X-Virus-Found: No AI05-0022 requires that tampering checks be performed in order to detect manipulation of the container via generic actual subprograms. (In the case of the ordered maps, that would occur through generic operators "<" for Key_Type and "=" for Element_Type.) However, for an empty container, no such check is strictly required, as we obtain the result without having to invoke any generic formal subprograms (because there are no elements). To ensure that there is no unnecessary manipulation of container state, we handle an empty container as a special case, and return a result immediately, without performing a tampering check. Tested on x86_64-pc-linux-gnu, committed on trunk 2013-04-25 Matthew Heaney * a-rbtgbo.adb, a-crbtgo.adb (Generic_Equal): do not test for tampering when container empty. * a-crbtgk.adb (Ceiling, Find, Floor): ditto. (Generic_Conditional_Insert, Generic_Conditional_Insert_With_Hint): ditto. Index: a-crbtgk.adb =================================================================== --- a-crbtgk.adb (revision 198221) +++ a-crbtgk.adb (working copy) @@ -45,6 +45,13 @@ X : Node_Access; begin + -- If the container is empty, return a result immediately, so that we do + -- not manipulate the tamper bits unnecessarily. + + if Tree.Root = null then + return null; + end if; + -- Per AI05-0022, the container implementation is required to detect -- element tampering by a generic actual subprogram. @@ -87,6 +94,13 @@ Result : Node_Access; begin + -- If the container is empty, return a result immediately, so that we do + -- not manipulate the tamper bits unnecessarily. + + if Tree.Root = null then + return null; + end if; + -- Per AI05-0022, the container implementation is required to detect -- element tampering by a generic actual subprogram. @@ -137,6 +151,13 @@ X : Node_Access; begin + -- If the container is empty, return a result immediately, so that we do + -- not manipulate the tamper bits unnecessarily. + + if Tree.Root = null then + return null; + end if; + -- Per AI05-0022, the container implementation is required to detect -- element tampering by a generic actual subprogram. @@ -198,6 +219,15 @@ -- its previous neighbor, in order for the conditional insertion to -- succeed. + -- Handle insertion into an empty container as a special case, so that + -- we do not manipulate the tamper bits unnecessarily. + + if Tree.Root = null then + Insert_Post (Tree, null, True, Node); + Inserted := True; + return; + end if; + -- We search the tree to find the nearest neighbor of Key, which is -- either the smallest node greater than Key (Inserted is True), or the -- largest node less or equivalent to Key (Inserted is False). @@ -227,9 +257,9 @@ if Inserted then - -- Either Tree is empty, or Key is less than Y. If Y is the first - -- node in the tree, then there are no other nodes that we need to - -- search for, and we insert a new node into the tree. + -- Key is less than Y. If Y is the first node in the tree, then there + -- are no other nodes that we need to search for, and we insert a new + -- node into the tree. if Y = Tree.First then Insert_Post (Tree, Y, True, Node); @@ -316,18 +346,26 @@ -- is not a search and the only comparisons that occur are with -- the hint and its neighbor. - -- If Position is null, this is interpreted to mean that Key is - -- large relative to the nodes in the tree. If the tree is empty, - -- or Key is greater than the last node in the tree, then we're - -- done; otherwise the hint was "wrong" and we must search. + -- Handle insertion into an empty container as a special case, so that + -- we do not manipulate the tamper bits unnecessarily. + if Tree.Root = null then + Insert_Post (Tree, null, True, Node); + Inserted := True; + return; + end if; + + -- If Position is null, this is interpreted to mean that Key is large + -- relative to the nodes in the tree. If Key is greater than the last + -- node in the tree, then we're done; otherwise the hint was "wrong" and + -- we must search. + if Position = null then -- largest begin B := B + 1; L := L + 1; - Compare := - Tree.Last = null or else Is_Greater_Key_Node (Key, Tree.Last); + Compare := Is_Greater_Key_Node (Key, Tree.Last); L := L - 1; B := B - 1; Index: a-crbtgo.adb =================================================================== --- a-crbtgo.adb (revision 198221) +++ a-crbtgo.adb (working copy) @@ -646,6 +646,13 @@ return False; end if; + -- If the containers are empty, return a result immediately, so as to + -- not manipulate the tamper bits unnecessarily. + + if Left.Length = 0 then + return True; + end if; + -- Per AI05-0022, the container implementation is required to detect -- element tampering by a generic actual subprogram. Index: a-rbtgbo.adb =================================================================== --- a-rbtgbo.adb (revision 198221) +++ a-rbtgbo.adb (working copy) @@ -626,6 +626,13 @@ return False; end if; + -- If the containers are empty, return a result immediately, so as to + -- not manipulate the tamper bits unnecessarily. + + if Left.Length = 0 then + return True; + end if; + -- Per AI05-0022, the container implementation is required to detect -- element tampering by a generic actual subprogram.