openldap-devel October 2014

openldap-devel@openldap.org

5 participants
10 discussions

LMDB crash consistency, again
by Howard Chu 05 Jan '15

05 Jan '15

This paper https://www.usenix.org/conference/osdi14/technical-sessions/presentation/zh… describes a potential crash vulnerability in LMDB due to its use of fdatasync instead of fsync when syncing writes to the data file. The vulnerability exists because fdatasync omits syncs of the file metadata; if the data file needed to grow as a result of any writes then this requires a metadata update. This is a well-understood issue in LMDB; we briefly touched on it in this earlier email thread http://www.openldap.org/lists/openldap-technical/201402/msg00111.html and it's been a topic of discussion on IRC ever since the first multi-FS microbenchmarks we conducted back in 2012. http://symas.com/mdb/microbench/july/ It's worth noting that this vulnerability doesn't exist on Windows, MacOSX, Android, or *BSD, because none of these OSs have a function equivalent to fdatasync in the first place - they always use fsync (or the Windows equivalent). (Android is an oddball; the underlying Linux kernel of course supports fdatasync, but the C library, bionic, does not.) We have a couple approaches for Linux: 1) provide an option to preallocate the file, using fallocate(). Unfortunately this doesn't completely eliminate metadata updates - filesystem drivers tend to try to be "smart" and make fallocate cheap; they allocate the space in the FS metadata but they also mark it as "unseen." The first time a process accesses an unseen page, it gets zeroed out. Up until that point, whatever old contents of the disk page are still present. The act of marking a page from "unseen" to "seen" requires a metadata update of its own. We had a discussion of this FS mis-feature a while ago, but it was fruitless. https://lkml.org/lkml/2012/12/7/396 2) preallocate the file by explicitly writing zeros to it. This has a couple other disadvantages: a) on SSDs, doing such a write needlessly contributes to wearout of the flash. b) Windows detects all-zero writes and compresses them out, creating a sparse file, thus defeating the attempt at preallocation. 3) track the allocated size of the file, and toggle between fsync and fdatasync depending on whether the allocated size actually grows or not. This is the approach I'm currently taking in a development branch. Whether we add this to a new 0.9.x release, or just in 1.0, I haven't yet decided. As another footnote, I plan to add support for LMDB on a raw partition in 1.x. Naturally, fsync vs fdatasync will be irrelevant in that case. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

2 9

Don't Use Copy Control (1.3.6.1.4.1.4203.666.5.15 vs. 1.3.6.1.1.22)
by Michael Ströder 30 Oct '14

30 Oct '14

HI! Is there any issue with using OID 1.3.6.1.1.22 as controlType for Don't Use Copy Control as defined in RFC 6171? Currently an experimental OpenLDAP .666 OID s used which makes this control rather unusable outside OpenLDAP implementation. Ciao, Michael.

3 8

test
by Quanah Gibson-Mount 30 Oct '14

30 Oct '14

testing... Earlier email never showed up. --Quanah -- Quanah Gibson-Mount Server Architect Zimbra, Inc. -------------------- Zimbra :: the leader in open source messaging and collaboration

1 0

slapd as an appliance
by Howard Chu 29 Oct '14

29 Oct '14

A couple different random thoughts all collided so I thought I'd jot them down here... We can have back-mdb/LMDB set the PROT_EXEC permission on the mmap, and then store executable code in LDAP entries and execute them directly. The idea came to me while reading about just-in-time C compilers and remembering my previous plans for liblforth. At first I was thinking only of small plugins (e.g. syntax parsers/normalizers) but really there's no reason that you couldn't handle larger executables the same way. I.e., we could store all of slapd's dynamically loadable modules in a back-mdb backend, change olcModuleLoad to use a DN, and dynamically insert and delete code on the fly, without needing any filesystem interactions. Once you have a system where all administrative operations can be done through LDAP, without requiring any other admin interface, it becomes pretty trivial to drop it into a sealed black box and deploy an "appliance." This would be a pretty key advantage for a small, self-contained embedded processor. Of course, it doesn't stop there - if the only system interface needed is the LDAP port, we don't even need a full OS distro any more. We could run slapd as process #1 (who needs systemd?) - a hardened system with zero unexpected attack surfaces, only one network port open to the world. One of the current in-progress items for LMDB is to enable using it on raw disk partitions. Adding this feature would mean you no longer have to worry about what type of filesystem to choose, or how to format it before setting up a database. Again, it would be ideal for an appliance because you'd just have to plugin a storage device and then create a back-mdb backend pointing to it. Another item for LMDB, once raw partition support is working, is in-kernel LMDB. Initially my motivation was to reproduce the KBDBFS work - an in-kernel filesystem built on top of BerkeleyDB (see here http://www.fsl.cs.sunysb.edu/docs/kbdbfs-msthesis/ ) but there's no need to stop there. We could port all of slapd into the kernel, and have a turnkey appliance with no user processes at all. Food for thought... -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

2 1

write-scaling problems in LMDB
by Luke Kenneth Casson Leighton 20 Oct '14

20 Oct '14

http://symas.com/mdb/inmem/scaling.html i just looked at this and i have a sneaking suspicion that you may be running into the same problem that i encountered when accidentally opening 10 LMDBs 20 times by forking 30 processes *after* opening the 10 LMDBs... (and also forgetting to close them in the parent). what i found was that when i reduced the number of LMDBs to 3 or below, the loadavg on the multi-core system was absolutely fine [ok, it was around 3 to 4 but that's ok] adding one more LMDB (remember that's 31 extra file handles opened to a shm-mmap'd file) increased the loadavg to 6 or 7. by the time that was up to 10 the loadavg had completely unreasonably jumped to over 30. i could log in over ssh - that was not a problem. editing a file was ok (opening it) but trying to create new files resulted in applications (such as vim) was blocked so badly that i often could not even press ctrl-z in order to background the task, and had to kill the entire ssh session. in each test run the amount of work being done was actually relatively small. basically i suspect a severe bug in the linux kernel which these extreme circumstances (32 or 16 processes accessing the same mmap'd file for example) have never been encountered, so the bug is simply... unknown. can i make the suggestion that, whilst i am aware that it is generally not recommended for production environments to run more processes than there are cores, you try running 128, 256 and even 512 processes all hitting that 64-core system, and monitor its I/O usage (iostats) and loadavg whilst doing so? the hypothesis to test is that the performance, which should scale reasonably linearly downwards as a ratio of the number of processes to the number of cores, instead drops like a lead balloon. l.

2 13

LMDB app-level crash consistency
by Howard Chu 17 Oct '14

17 Oct '14

For posterity, this is the conversation we had with the University of Wisconsin researchers behind this Usenix OSDI paper: https://www.usenix.org/conference/osdi14/technical-sessions/presentation/pi… > On Thu, Jul 24, 2014 at 8:10 AM, Howard Chu <hyc(a)symas.com > <mailto:hyc@symas.com>> wrote: > > Hello Thanu, > I just saw your slides from > http://wisdom.cs.wisc.edu/__index.htm#news-2 > <http://wisdom.cs.wisc.edu/index.htm#news-2> and was wondering if you > could give more details on the crash vulnerabilities you found in LMDB. > Thanks. 25/07/14 09:42 Thanumalayan Sankaranarayana Pillai wrote: > > Hi Howard, > > > > Thanks for your interest in the slides. We appreciate you caring about the > > vulnerability. > > The single crash vulnerability that we discovered in LMDB concerns the > 106-byte update to the header while inserting a key-value pair (within the > mdb_txn_commit function). Specifically, if this overwrite is not done > atomically (i.e., if only a part of the 106 bytes goes to disk, and then a > crash happens), then LMDB reports an error if we try to further modify the > database after reboot. The error reported is "mdb_page_touch: Assertion > `mp->mp_p.p_pgno != pgno' failed". > > We also did some manual analysis by making the loss in atomicity correspond to > field boundaries within the information contained in those 106-bytes (such as > free list data and transaction ID), and found that LMDB loses the previous > transaction sometimes. For example, if the database contains Txn-1, Txn-2, and > Txn-3, and a crash happens while inserting Txn-4, the rebooted-database might > lose Txn-3. I have not included any such manual analysis results in the slides. > > I have attached a text file with a more detailed description of the > vulnerability. If you have any questions on the details, I have CC'ed Ram, who > actually tested LMDB for the vulnerabilities and might be able to help you > better than me. > > Thus, the vulnerability in LMDB relates to the atomicity of a file overwrite > that is within a 512-byte sector. With current (ext3/ext4/btrfs/xfs/zfs) file > systems running atop hard drives and SSDs, this is probably not a problem. > (The only place we have heard about that indicates atomicity might not be > maintained here is [1]). > > However, byte-accessible NVRAMs in the future will probably expose this > vulnerability. We are also not sure what happens with the multi-level storage > stacks many people use these days (Virtual machines atop Fusion-IO-card > connected via networks to a NAS?). In our understanding, even for these > situations, LMDB can solve this vulnerability easily, since it has two root > pointers. > > All said, since we are not particularly experts at using LMDB, there is a > slight chance we made a mistake in how we used LMDB while testing it. Please > let us know if you suspect this to be the case. Hope this helps! > > [1] http://lkml.iu.edu//hypermail/linux/kernel/0908.3/00155.html > > -- > Thanks, > Thanu 25/07/14 11:38 Howard: > Thanks much for your reply. The results you describe are not too surprising; > we assume atomic sector writes. This is an area we've spent quite a lot of > time researching ourselves. I summarized our findings here last year > http://www.openldap.org/its/index.cgi/Incoming?id=7668 > > Currently all hard drive/SSD manufacturers guarantee that 512 byte sector > writes are atomic. As such, failure to write the 106 byte header is not > something we account for in current LMDB releases. Also, failures of this type > should result in ECC errors in the disk sector - it should be impossible to > successfully read a sector that was written incorrectly in the ways you describe. > > Even in extreme cases, the probability of failure to write the leading 128 out > of 512 bytes of a sector is nearly nil - even on very old hard drives, before > 512-byte sector write guarantees. We would have to go back nearly 30 years to > find such a device, e.g. > > http://bitsavers.informatik.uni-stuttgart.de/pdf/quantum/Quantum_ProDrive_4… > > Page 23, Section 2.1 > "No damage or loss of data will occur if power is applied or removed during > drive operation, except that data may be lost in the sector being written at > the time of power loss." > > From the specs on page 15, the data transfer rate to/from the platters is > 1.25MB/sec, so the time to write one full sector is 0.4096ms; the time to > write the leading 128 bytes of the sector is thus 1/4 of that: 0.10ms. You > would have to be very very unlucky to have a power failure hit the drive > within this .1ms window of time. Fast-forward to present day and it's simply > not an issue. > > But as you say, byte-addressable storage is coming soon. The LMDB 1.x versions > will add a checksum to the two headers, and will fallback to using the > previous header if a checksum error is found. > > Thanks again for your work, looking forward to reading your full paper in the > future. 25/07/14 13:14 Thanu: > Hi Howard, > > Great to know that so much thought was already put into this issue. (We usually see people assume things about the storage stack that are simply false, and without any notion of when they will become false if they aren't already.) I am waiting for all the cool new things that will be on LMDB 1.0. > > Thanks, > Thanu 25/07/14 13:15 Howard: > Hi again, > looking over these vulnerabilities, they all seem unrealistic even given > the existence of byte-addressable storage devices. In particular, even if you > assume writes may be non-atomic, why do you assume that writes will be > non-sequential within a sector? > > For example, if we were talking about an HDD that did not guarantee atomic > sector writes, we still know that bytes are written sequentially from > beginning of sector to end of sector; this is one reason why the LMDB meta > page is laid out in the way that it is - the transaction ID is last because if > a partial write occurs and the txn ID doesn't make it to disk, this meta page > will be ignored and the previous one will be used automatically. > > In the tests you describe here, you have broken this sequential assumption, > but there are no storage devices in existence that can fail in the manners you > describe. And even in byte-addressable memories, DMA or memcpy routines will > always start at a low-numbered address and work sequentially higher. Do you > really believe it is important for software to protect against this type of > failure scenario? >> > Found using automatic analysis >> > ------------------------------ >> > >> > Write (106 bytes) at lib/mdb.c:3227[mdb_txn_commit]. Split into three, first part (first 36 bytes) alone does not go to disk. >> > >> > Error: lib/mdb.c:1921: mdb page touch: Assertion ‘mp->mp p.p pgno != pgno’ failed. >> > >> > Exact situations where the vulnerabilities arise, found using manual analysis >> > ----------------------------------------------------------------------------- >> > >> > 1. Only txn id gets into metapage and no other data: >> > >> > Previous transaction is lost. >> > >> > 2. Free list data, txn id and last page goes in but not main db details: >> > >> > Previous transaction is lost. Error: lib/mdb.c:1921: mdb page touch: Assertion ‘mp->mp p.p pgno != pgno’ failed. >> > >> > 3. only main db - 2 fields no free pointer: >> > >> > Error: lib/mdb.c:1921: mdb page touch: Assertion ‘mp->mp p.p pgno != pgno’ failed. >> > >> > 4. Everything gets in except database pointer - it is 48 bytes - but a crash happens such that second 24 bytes (which contains the root) is missed: >> > >> > Previous transaction is lost. Error: lib/mdb.c:1921: mdb page touch: Assertion ‘mp->mp p.p pgno != pgno’ failed. 25/07/14 14:03 Thanu: > Hi Howard, > > To be honest, we are not yet sure whether it is important for software to protect sequential-assumption-breaking under practical circumstances. While byte-addressable devices might only persist things sequentially, a byte-addressable file system itself might re-order bytes (what if the memcpy doesn't start from the lower address?); at this point however, I am probably being cynical and hypothesizing too much about the future. > > However there is currently no standard/guarantee that (file-system-level) writes should be sequential or atomic as far as we know. One of our goals in doing this project is to show the entire community how non-standardized the interaction between the application and the file system is. It is fully possible that, by the time NVMs become main-stream, standards arise and sector-size non-sequential (or even non-atomic) writes are disallowed. (It might also be possible that someone invents an NVM with high parallel bandwidth, and memcpy() explicitly parallelizes updates to contiguous bytes for higher throughput.) > > Personally, with software such as LMDB, I feel that we should simply add a CRC, just in case future storage stacks behave in "reasonably weird" ways. I do understand that it might be better to not do this for either readability or performance and simply keep an eye out for any new storage stacks. > > If it is not too much trouble, can you point me to any discussions about byte-addressable storage being sequential? I have heard this mentioned once before, but I cannot find any solid references to it. Any references to sequentiality within HDDs will be useful as well. > > Thanks, > Thanu On Fri, Jul 25, 2014 at 8:50 AM, Howard Chu <hyc(a)symas.com wrote: >>> Regarding sequentiality within HDDs, that's a natural consequence of the >>> physical construction/operation of HDDs. The platters rotate under the R/W >>> head, the R/W head spits out a stream of bits in sequential order. The >>> platter always rotates in one direction, at essentially constant speed, so >>> the R/W head cannot skip back and forth within 1 sector and write out of >>> order. It's physically impossible for HDDs to write non-sequentially >>> within a single sector. >>> >>> For your reference re: SSDs, here's an old Samsung NAND Flash data sheet. >>> http://pdf1.alldatasheet.com/__datasheet-pdf/view/84340/__SAMSUNG/K9F1G08U0… >>> <http://pdf1.alldatasheet.com/datasheet-pdf/view/84340/SAMSUNG/K9F1G08U0A.ht…> >>> >>> The relevant info is page 31 "Page Program" >>> "The device is programmed basically on a page basis, but it does allow >>> multiple partial page programing of a word or consecutive >>> bytes up to 2112, in a single page program cycle. The number of >>> consecutive partial page programming operation within the same >>> page without an intervening erase operation must not exceed 4 times for >>> main array(1time/512byte) and 4 times for spare >>> array(1time/16byte). The addressing should be done in sequential order in >>> a block." >>> >>> For byte-addressable storage I suppose no hard rules apply. If we're >>> talking about NVDIMMs, they are treated basically the same as DRAM. Still, >>> in Linux today you're most likely to see a block-device style layer >>> imposed above them. DMA controllers tend to be programmed for >>> auto-incrementing addresses. memcpy will tend to do the same, since CPU >>> prefetchers are also designed with at least cache-line sequentiality. >>> I.e., it may not be important to write to the destination in sequential >>> order, but there is a performance benefit to reading from the source in >>> sequential order, and there is no benefit to holding the read and >>> reordering it before pushing to the destination. >>> 25/07/14 15:46 Thanu: > Hi Howard, > > Thanks for the explanation and the pointers. They are really helpful. > > While you certainly have more working knowledge of byte-addressable > storage than me, I still believe there is an (extremely) small chance of non-sequential updates on Linux. Let us say that the cache block is 64 bytes in size, and the block-device layer modifies the mapped memory addresses corresponding to all user writes. For argument's sake, let us also say that writes are written back to the actual storage if there is a change in the (coherence) ownership of a cache block. If we consider two adjacent 64-byte blocks, and the second block is written twice by different cores, it is possible that the second block reaches the storage first. > > Of course, even if such non-sequential updates become possible in the future, it would require changes to the file-system journaling machinery itself, and is bound to be well-publicized. I am only justifying why we considered non-sequential updates in our study (to measure the impact of such scenarios on applications). We are hoping that if someone in the future (ever) debates about introducing non-atomic updates, they fully understand the application-level consequences by looking at our study. > > Thanks, > Thanu 25/07/14 16:46 Howard: > Fair enough. Certainly, if the question ever arose, I would be glad we have > your study to point to as a reference. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

1 0

question about use of buffers in lmdb
by Luke Kenneth Casson Leighton 17 Oct '14

17 Oct '14

howard, et al, hi, i notice that LMDB stores data in an "append only" manner (from the Q&A). i was thinking of recommending that in python the buffers be handed around with *direct* and persistent pointers to the data within the LMDB shm/memory-map. the reason that i believe this will be successful is because the circumstances are rather unusual: once data is entered (added) it is *never* overwritten, updated, changed, or modified. there simply is no need [in this application]. so there will only ever be insertion (once and only once) or controlled and monitored deletion (by age of record). under these circumstances is it perfectly reasonable to pass around the pointers to the buffers returned from value look-ups *indefinitely*? if so that would be awesome. l.

2 2

Notice to move the Fortress source to Apache Directory project
by Shawn McKinney 08 Oct '14

08 Oct '14

Hello, This is a notice of intent to move the following sources to apache directory project: 1. fortress core 2. realm 3. emnasse 4. commander The goal is to expand user adoption and gain commiters by working alongside projects of a similar nature, i.e. syncope, shiro, studio, etc. Over the past three years I have enjoyed the benefits of these sources being housed within the openldap project and will continue to promote fortress using openldap directory server as before. Indeed there are projects in our pipeline (rbac accelerator overlay) that will (should) remain under the openldap umbrella so my participation with openldap project will continue for the forseeable future. Shawn McKinney -- 650-963-7681 smckinney(a)symas.com

1 0

On-demand page mapping in LMDB
by Howard Chu 01 Oct '14

01 Oct '14

The vl32 branch on gitorious has some tweaks for LMDB to mmap on individual page accesses, instead of mmap'ing the entire DB file all at once. This is primarily to support usage on 32 bit machines, where the address space is too small to accomodate multiple DBs mapped in competely, all at once. https://gitorious.org/mdb/mdb/source/69d7cb8d44e04f02d8d0c923ae71fbaaa9f42f…: There's a significant performance hit since almost every page reference results in an mmap system call. But it also has a much smaller memory footprint. While the code passes simple tests, it is also broken in one significant aspect: Currently, advancing a cursor to a new page causes the previous page to be unmapped. If there are two cursors open on the same DBI in the same transaction, it's possible that the other cursor will still be pointed to the old page, and the unmap will break it. There's currently no check to prevent this, and since read txns don't track all of their open cursors, there is no way to check (unless we add refcounts to this array, which would be clumsy). The solution I'm considering is to get rid of the per-txn array of mapped pages that I added here, and just operate on the cursor stacks directly. In that case, every cursor will have its own set of mapped read-only pages, and nothing that happens on one cursor will have any effect on any other cursor. (For read-only pages. For dirty pages, the usual cursor/page fixups apply as always.) -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

1 0

Incremental backup in LMDB
by Howard Chu 01 Oct '14

01 Oct '14

A preliminary branch has been available on gitorious for a few months. It has some issues though, which still need to be resolved. https://gitorious.org/mdb/mdb/source/a7fc32c0b39c29f9afd2172338060b079d549c…: The biggest problem is that scanning every page of the DB is unsafe - if a page was an overflow page, and was freed and partially reused, then a scan may walk into intermediate chunks of data (which won't have valid page headers, although the data might coincidentally appear to have them). Two approaches to solving this are to perform the scan, but ignore pages that are currently listed in the freeDB, or to do a regular tree walk instead. At the moment I'm leaning toward just walking the trees. If the freeDB is large then comparing every scanned page to the freeDB could be expensive. Also, newer pages of the freeDB itself must be copied as well, and this would mean freeDB pages get read twice. Just thinking out loud here to document what we discussed before in IRC, so it doesn't get lost in the meantime. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

1 0

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

openldap-devel October 2014