From mboxrd@z Thu Jan 1 00:00:00 1970 From: Michael Tremer To: location@lists.ipfire.org Subject: libloc: Approaching feature-completeness Date: Fri, 04 Oct 2019 10:15:55 +0100 Message-ID: <05EDD781-CED3-421A-A614-12EBFB1EBCA7@ipfire.org> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============2025949264772480848==" List-Id: --===============2025949264772480848== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Good morning ladies and gentlemen, I would like to bring everyone up to speed since we have made huge progress o= n libloc and I would like to keep this momentum! What has happened in the last couple of weeks? Stefan has been working on Perl bindings which are essential to launch this o= n IPFire 2. The web UI makes a lot of use of looking up IP addresses and disp= laying the correct flag. That needs to be fast and therefore we could not rel= y on a CLI wrapper for location-query(8). The Perl module is super-lightweight and does not implement all features of l= ibloc. Mainly it is ready-only since we do not need another tool to compose a= database. For our purposes this is sufficient and easier to maintain. If any= one else needs more features, they can always be added later. The other thing I have been working on (with a lot of sweat, blood and tears)= is walking through the tree to search it. This has been an outstanding issue= for a long time and was fairly difficult to implement since a standard DFS w= as not possible to use. We have encoded information into the edges to store l= ess information and this made it extremely difficult to extract again - on to= p of that comes that the implementation could not be recursive to be used in = the Python wrapper. We now have a re-entrant search which performs super fast= and uses very little memory. The depth of the tree is limited to 128, althou= gh we would never get too close to that. That results in a maximum stack size= of 256 + 1 nodes and we walk through every edge and node only once which res= ults in a performance of O(1) for computing and memory. It could not get bett= er than that. Finally, I have extended the Python bindings to make use of all of this so th= at all networks belonging to an AS can now be listed with =E2=80=9Clist-netwo= rks-by-as=E2=80=9D and all networks belonging to a country can be listed with= =E2=80=9Clist-networks-by-cc=E2=80=9D. I have added a man-page for location-query(8) which can be found here: https://man-pages.ipfire.org/libloc/location-query.html As far as I can see this now, we are approaching to be feature-complete for a= 1.0 release. Of course there is still a long way to test this and make sure that we do not= have any bugs in the database format or the code. Another major road block is that we do not have a database that is ready for = prime time, yet, but the good news is that the toolkit is almost there! Best, -Michael --===============2025949264772480848==--