From patchwork Mon Jul 24 21:18:09 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sven Eckelmann X-Patchwork-Id: 17075 Return-Path: X-Original-To: patchwork@open-mesh.org Delivered-To: patchwork@open-mesh.org Received: from open-mesh.org (localhost [IPv6:::1]) by open-mesh.org (Postfix) with ESMTP id 62082817F3; Mon, 24 Jul 2017 23:18:23 +0200 (CEST) Authentication-Results: open-mesh.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=narfation.org header.i=@narfation.org header.b="kg7dVc4i"; dkim-atps=neutral Received: from v3-1039.vlinux.de (narfation.org [79.140.41.39]) by open-mesh.org (Postfix) with ESMTPS id 60E1D80933 for ; Mon, 24 Jul 2017 23:18:21 +0200 (CEST) Received: from sven-edge.localnet (p200300C593C30400611216DF1E13517C.dip0.t-ipconnect.de [IPv6:2003:c5:93c3:400:6112:16df:1e13:517c]) by v3-1039.vlinux.de (Postfix) with ESMTPSA id 08DEF1100E7 for ; Mon, 24 Jul 2017 23:18:20 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=narfation.org; s=20121; t=1500931101; bh=gClQWHamFnrewWNP3o3OSX5p26qmPZDy9MbeBsNCW64=; h=From:To:Subject:Date:From; b=kg7dVc4iFMgAkYMqaicbIP7FMEsLLrNTk192WNqmfbq7P1PrBuQ6ju+250968spNg DKAk7D4iRam/82mgw21yx5OwJURYnCOdtXUujygVmrdztnQb4zgo8RI/hwD+BfeZ/c dr0OLmuAq4vx3TTR/D+xP8iaAAQNiGGvYOZ+hhqI= From: Sven Eckelmann To: b.a.t.m.a.n@lists.open-mesh.org Date: Mon, 24 Jul 2017 23:18:09 +0200 Message-ID: <13899415.9hl4lahuAs@sven-edge> User-Agent: KMail/5.2.3 (Linux/4.9.0-3-amd64; KDE/5.28.0; x86_64; ; ) MIME-Version: 1.0 Subject: [B.A.T.M.A.N.] [PATCH 0/2] alfred: Use bitmap to store dataset change events X-BeenThere: b.a.t.m.a.n@lists.open-mesh.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: The list for a Better Approach To Mobile Ad-hoc Networking List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: The list for a Better Approach To Mobile Ad-hoc Networking Errors-To: b.a.t.m.a.n-bounces@lists.open-mesh.org Sender: "B.A.T.M.A.N" Hi, the --update-command implementation looked quite memory inefficient to me and I have therefore replaced it using a simple bit map which stores in BIT(i) when datatype I was modified. Here from the second patch: > The implementation for --update-command uses a double linked list to store > the detected modifications of datasets. This implementation requires 24 > bytes (1 byte data type, 7 bytes padding, 16 bytes linked list pointers) on > amd64 for each element of the list. Each modified dataset type requires an > own list item. Each list item is allocated using malloc and therefore > additional overhead for the libc allocator information has also to be > stored next to it. The list head uses a similar amount of memory (16 byte > list pointers, 2 byte counter, 6 byte padding) but doesn't require > additional allocations. > > The list based implementation provides information about modified dataset > type and the order in which these modifications were detected. But the > latter is not actually required fr --update-command and can therefore be > omitted. > > A simple 256 bit wide storage element (32 bytes) is enough to keep the > required information when only the detected modified data types have to be > registered. BIT(i) is either 1 when dataset type i was modified or 0 when > no modification was detected. This removes the (de)allocation CPU + memory > overhead and avoids list searches when adding newly detected modifications. The bitops.h file is used to implement the bit operations and keep the details away from the server code. I've reduced the size of the header file a little bit because most of it was not used by alfred. Kind regards, Sven Sven Eckelmann (2): alfred: Use constant to define data type range alfred: Use bitmap to store dataset change events alfred.h | 4 +- bitops.h | 379 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ main.c | 9 +- packet.h | 1 + server.c | 46 ++++---- 5 files changed, 406 insertions(+), 33 deletions(-) create mode 100644 bitops.h