summaryrefslogtreecommitdiffstats
path: root/xlators/protocol/client
Commit message (Collapse)AuthorAgeFilesLines
* protocol/client: fallback to anonymous fd for fsyncl17zhou2020-03-101-2/+4
| | | | | Change-Id: I32f801206ce7fbd05aa693f44c2f140304f2e275 Fixes: bz#1810842
* protocol/client: structure loggingyatip2020-03-036-71/+83
| | | | | | | | | convert gf_msg() to gf_smsg() Updates: #657 Change-Id: I76a09cfd283bb4ec5c4358536da66547aaf0de31 Signed-off-by: yatip <ypadia@redhat.com>
* dht: Fix stale-layout and create issueSusant Palai2020-02-091-4/+5
| | | | | | | | | | | | | | | | | Problem: With lookup-optimize set to on by default, a client with stale-layout can create a new file on a wrong subvol. This will lead to possible duplicate files if two different clients attempt to create the same file with two different layouts. Solution: Send in-memory layout to be cross checked at posix before commiting a "create". In case of a mismatch, sync the client layout with that of the server and attempt the create fop one more time. test: Manual, testcase(attached) fixes: bz#1786679 Change-Id: Ife0941f105113f1c572f4363cbcee65e0dd9bd6a Signed-off-by: Susant Palai <spalai@redhat.com>
* protocol/client-rpc-fops: structure loggingyatip2020-02-062-350/+278
| | | | | | | | | convert all gf_msg() to gf_smsg() Updates: #657 Change-Id: Ia9d4fb17579af6586bc13d69ec7990c6cf220aac Signed-off-by: yatip <ypadia@redhat.com>
* protocol/client: Maintain connection to brick statusPranith Kumar K2020-02-052-7/+5
| | | | | | | | | | | | | | | | Problem: The current version of the code depends on the non-zero-port information to propagate ping event from brick to parent layers. But as and when connection succeeds, port is set to zero in rpc layer.So ping event is never propagated to parent layers. Halo doesn't work without this. Fix: Remember the status of connection in 'private' structure and use that to decide to propagate ping event to parent xlator. fixes: bz#1797934 Change-Id: Ia578ba9fb3813953d2068dbba5c982ab27cc3429 Signed-off-by: Pranith Kumar K <pkarampu@redhat.com>
* protocol/client: structure loggingyatip2020-02-042-78/+88
| | | | | | | | | convert all gf_msg() to gf_smsg() Updates: #657 Change-Id: I69b228d7c7a8bc6263f9bd33710e880678d8c017 Signed-off-by: yatip <ypadia@redhat.com>
* protocol/client-handshake: structure loggingyatip2020-02-042-175/+170
| | | | | | | | | convert gf_msg() to gf_smsg() Updates: #657 Change-Id: Iee07228cfc3a9a9cd10e89ae9eb918681b072585 Signed-off-by: yatip <ypadia@redhat.com>
* protocol/client-rpc-fops_v2: structure loggingyatip2020-02-042-216/+168
| | | | | | | | | convert gf_msg() to gf_smsg() Updates: #657 Change-Id: Ib45f121f583c2af09bfddb23391f73a117e63213 Signed-off-by: yatip <ypadia@redhat.com>
* server: Mount fails after reboot 1/3 gluster nodesMohit Agrawal2020-01-221-2/+1
| | | | | | | | | | | | | | | | | Problem: At the time of coming up one server node(1x3) after reboot client is unmounted.The client is unmounted because a client is getting AUTH_FAILED event and client call fini for the graph.The client is getting AUTH_FAILED because brick is not attached with a graph at that moment Solution: To avoid the unmounting the client graph throw ENOENT error from server in case if brick is not attached with server at the time of authenticate clients. Credits: Xavi Hernandez <xhernandez@redhat.com> Change-Id: Ie6fbd73cbcf23a35d8db8841b3b6036e87682f5e Fixes: bz#1793852 Signed-off-by: Mohit Agrawal <moagrawa@redhat.com>
* dictionary: remove the 'extra_free' parameterYaniv Kaul2020-01-211-11/+4
| | | | | | | | | | | | | | | This parameter may have been used in the past, but is no longer needed. Removing it and the few locations it was actually referenced. This allows to remove an extra memdup as well, that was not needed in the 1st place in server_setvolume() and unserialize_rsp_direntp() functions. A followup separate patch will remove extra_stdfree parmeter from the dictionary structure. Change-Id: Ica0ff0a330672373aaa60e808b7e76ec489a0fe3 updates: bz#1193929 Signed-off-by: Yaniv Kaul <ykaul@redhat.com>
* protocol/client: Fix a log entryAnoop C S2020-01-151-1/+1
| | | | | | | | | It has been a while since we removed lock healing logic from protocol client. So no need to mention that we healed locks after fd reopen. Change-Id: I24bd3f9e9f2942e306714b2cb83c229ae57c60ae Fixes: bz#1193929 Signed-off-by: Anoop C S <anoopcs@redhat.com>
* debug/io-stats: add an option to set volume-idAmar Tumballi2019-11-291-2/+5
| | | | | | | | | | | 'volume-id' is good to have for a graph for uniquely identifying it. Add it to graph->volume_id while generating volfile itself. This can be further used in many other places. Updates: #763 Change-Id: I80516d62d28a284e8ff4707841570ced97a37e73 Signed-off-by: Amar Tumballi <amar@kadalu.io>
* rpc: align structsYaniv Kaul2019-10-171-15/+15
| | | | | | | | | | | | | squash tens of warnings on padding of structs in afr structures. The warnings were found by manually added '-Wpadded' to the GCC command line. Also made relevant structs and definitions static, where it was applicable. Change-Id: Ib71a7e9c6179378f072d796d11172d086c343e53 updates: bz#1193929 Signed-off-by: Yaniv Kaul <ykaul@redhat.com>
* client xlator: misc. cleanupsYaniv Kaul2019-10-116-662/+474
| | | | | | | | | | | | | - remove dead code - move functions to be static - move some code that only needs to be executed under if branch - remove some dead assignments and redundant checks. No functional change, I hope. Change-Id: I93d952408197ecd2fa91c3f812a73c54242342fa updates: bz#1193929 Signed-off-by: Yaniv Kaul <ykaul@redhat.com>
* protocol/handshake: pass volume-id for extra checkAmar Tumballi2019-09-301-0/+50
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | With added check of volume-id during handshake, we can be sure to not connect with a brick if this gets re-used in another volume. This prevents any accidental issues which can happen with a stale client process lurking along. Also added test case for testing same volume name which would fetch a different volfile (ie, different bricks, different type), and a different volume name, but same brick. For reference: Currently a client<->server handshake happens in glusterfs through protocol/client translator (setvolume) to protocol/server using a dictionary which containes many keys. Rejection happens in server side if some of the required keys are missing in handshake dictionary. Till now, there was no single unique identifier to validate for a client to tell server if it is actually talking to a corresponding server. All we look in protocol/client is a key called 'remote-subvolume', which should match with a subvolume name in server volume file, and for any volume with same brick name (can be present in same cluster due to recreate), it would be same. This could cause major issue, when a client was connected to a given brick, in one volume would be connected to another volume's brick if its re-created/re-used. To prevent this behavior, we are now passing along 'volume-id' in handshake, which would be preserved for the life of client process, which can prevent this accidental connections. NOTE: This behavior wouldn't be applicable for user-snapshot enabled volumes, as snapshotted volume's would have different volume-id. Fixes: bz#1620580 Change-Id: Ie98286e94ce95ae09c2135fd6ec7d7c2ca1e8095 Signed-off-by: Amar Tumballi <amarts@redhat.com>
* protocol/client: don't reopen fds on which POSIX locks are held after a ↵Raghavendra G2019-09-127-6/+109
| | | | | | | | | | | | | | | | | | | reconnect Bricks cleanup any granted locks after a client disconnects and currently these locks are not healed after a reconnect. This means post reconnect a competing process could be granted a lock even though the first process which was granted locks has not unlocked. By not re-opening fds, subsequent operations on such fds will fail forcing the application to close the current fd and reopen a new one. This way we prevent any silent corruption. A new option "client.strict-locks" is introduced to control this behaviour. This option is set to "off" by default. Change-Id: Ieed545efea466cb5e8f5a36199aa26380c301b9e Signed-off-by: Raghavendra G <rgowdapp@redhat.com> updates: bz#1694920
* glusterd, rpc, glusterfsd: fix coverity defects and put required annotationsAtin Mukherjee2019-09-101-2/+6
| | | | | | | | | | | 1404965 - Null pointer dereference 1404316 - Program hangs 1401715 - Program hangs 1401713 - Program hangs Updates: bz#789278 Change-Id: I6e6575daafcb067bc910445f82a9d564f43b75a2 Signed-off-by: Atin Mukherjee <amukherj@redhat.com>
* graph/cleanup: Fix race in graph cleanupMohammed Rafi KC2019-09-051-2/+63
| | | | | | | | | | | | | | | | | We were unconditionally cleaning up the grap when we get child_down followed by parent_down. But this is prone to race condition when some of the bricks are already disconnected. In this case, even before the last child down is executed in the client xlator code,we might have freed the graph. Because the child_down event is alreadt recevied. To fix this race, we have introduced a check to see if all client xlator have cleared thier reconnect chain, and called the child_down for last time. Change-Id: I7d02813bc366dac733a836e0cd7b14a6fac52042 fixes: bz#1727329 Signed-off-by: Mohammed Rafi KC <rkavunga@redhat.com>
* logging: Structured logging reference PRAravinda VK2019-08-202-149/+127
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | To convert the existing `gf_msg` to `gf_smsg`: - Define `_STR` of respective Message ID as below(In `*-messages.h`) #define PC_MSG_REMOTE_OP_FAILED_STR "remote operation failed." - Change `gf_msg` to use `gf_smsg`. Convert values into fields and add any missing fields. Note: `errno` and `error` fields will be added automatically to log message in case errnum is specified. Example: gf_smsg( this->name, // Name or log domain GF_LOG_WARNING, // Log Level rsp.op_errno, // Error number PC_MSG_REMOTE_OP_FAILED, // Message ID "path=%s", local->loc.path, // Key Value 1 "gfid=%s", loc_gfid_utoa(&local->loc), // Key Value 2 NULL // Log End ); Key value pairs formatting Help: gf_slog( this->name, // Name or log domain GF_LOG_WARNING, // Log Level rsp.op_errno, // Error number PC_MSG_REMOTE_OP_FAILED, // Message ID "op=CREATE", // Static Key and Value "path=%s", local->loc.path, // Format for Value "brick-%d-status=%s", brkidx, brkstatus, // Use format for key and val NULL // Log End ); Before: [2019-07-03 08:16:18.226819] W [MSGID: 114031] [client-rpc-fops_v2.c \ :2633:client4_0_lookup_cbk] 0-gv3-client-0: remote operation failed. \ Path: / (00000000-0000-0000-0000-000000000001) [Transport endpoint \ is not connected] After: [2019-07-29 07:50:15.773765] W [MSGID: 114031] \ [client-rpc-fops_v2.c:2633:client4_0_lookup_cbk] 0-gv1-client-0: \ remote operation failed. [{path=/f1}, \ {gfid=00000000-0000-0000-0000-000000000000}, \ {errno=107}, {error=Transport endpoint is not connected}] To add new `gf_smsg`, Add a Message ID in respective `*-messages.h` file and the follow the steps mentioned above. Change-Id: I4e7d37f27f106ab398e991d931ba2ac7841a44b1 Updates: #657 Signed-off-by: Aravinda VK <avishwan@redhat.com>
* protocol/client - fixing a coverity issueBarak Sason2019-08-201-3/+3
| | | | | | | | | | Moved null pointer check up in order to avoid seg-fault CID: 1404258 Updates: bz#789278 Change-Id: Ib97e05302bfeb8fe38d6ce9870b9740cb576e492 Signed-off-by: Barak Sason <bsasonro@redhat.com>
* client-handshake.c: minor changes and removal of dead code.Yaniv Kaul2019-08-142-287/+54
| | | | | | | | | | - Removal of quite a bit of dead code. - Use dict_set_str_sizen and friends where applicable. - Moved some functions to be static and initialize values right away. Change-Id: Ic25b5da4028198694a0e24796dea375661eb66b9 updates: bz#1193929 Signed-off-by: Yaniv Kaul <ykaul@redhat.com>
* event: rename event_XXX with gf_ prefixedXiubo Li2019-07-291-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I hit one crash issue when using the libgfapi. In the libgfapi it will call glfs_poller() --> event_dispatch() in file api/src/glfs.c:721, and the event_dispatch() is defined by libgluster locally, the problem is the name of event_dispatch() is the extremly the same with the one from libevent package form the OS. For example, if a executable program Foo, which will also use and link the libevent and the libgfapi at the same time, I can hit the crash, like: kernel: glfs_glfspoll[68486]: segfault at 1c0 ip 00007fef006fd2b8 sp 00007feeeaffce30 error 4 in libevent-2.0.so.5.1.9[7fef006ed000+46000] The link for Foo is: lib_foo_LADD = -levent $(GFAPI_LIBS) It will crash. This is because the glfs_poller() is calling the event_dispatch() from the libevent, not the libglsuter. The gfapi link info : GFAPI_LIBS = -lacl -lgfapi -lglusterfs -lgfrpc -lgfxdr -luuid If I link Foo like: lib_foo_LADD = $(GFAPI_LIBS) -levent It will works well without any problem. And if Foo call one private lib, such as handler_glfs.so, and the handler_glfs.so will link the GFAPI_LIBS directly, while the Foo won't and it will dlopen(handler_glfs.so), then the crash will be hit everytime. The link info will be: foo_LADD = -levent libhandler_glfs_LIBADD = $(GFAPI_LIBS) I can avoid the crash temporarily by linking the GFAPI_LIBS in Foo too like: foo_LADD = $(GFAPI_LIBS) -levent libhandler_glfs_LIBADD = $(GFAPI_LIBS) But this is ugly since the Foo won't use any APIs from the GFAPI_LIBS. And in some cases when the --as-needed link option is added(on many dists it is added as default), then the crash is back again, the above workaround won't work. Fixes: #699 Change-Id: I38f0200b941bd1cff4bf3066fca2fc1f9a5263aa Signed-off-by: Xiubo Li <xiubli@redhat.com>
* (multiple files) use dict_allocate_and_serialize() where applicable.Yaniv Kaul2019-07-221-11/+3
| | | | | | | | This function does length, allocation and serialization for you. Change-Id: I142a259952a2fe83dd719442afaefe4a43a8e55e updates: bz#1193929 Signed-off-by: Yaniv Kaul <ykaul@redhat.com>
* protocol/client: propagte GF_EVENT_CHILD_PING only for connections to brickRaghavendra G2019-06-271-4/+12
| | | | | | | | | | | | | | | | | | | | | | | Two reasons: * ping responses from glusterd may not be relevant for Halo replication. Instead, it might be interested in only knowing whether the brick itself is responsive. * When a brick is killed, propagating GF_EVENT_CHILD_PING of ping response from glusterd results in GF_EVENT_DISCONNECT spuriously propagated to parent xlators. These DISCONNECT events are from the connections client establishes with glusterd as part of its reconnect logic. Without GF_EVENT_CHILD_PING, the last event propagated to parent xlators would be the first DISCONNECT event from brick and hence subsequent DISCONNECTS to glusterd are not propagated as protocol/client prevents same event being propagated to parent xlators consecutively. propagating GF_EVENT_CHILD_PING for ping responses from glusterd would change the last_sent_event to GF_EVENT_CHILD_PING and hence protocol/client cannot prevent subsequent DISCONNECT events Signed-off-by: Raghavendra G <rgowdapp@redhat.com> Fixes: bz#1716979 Change-Id: I50276680c52f05ca9e12149a3094923622d6eaef
* across: coverity fixesAmar Tumballi2019-06-031-0/+3
| | | | | | | | | | | | | | | * locks/posix.c: key was not freed in one of the cases. * locks/common.c: lock was being free'd out of context. * nfs/exports: handle case of missing free. * protocol/client: handle case of entry not freed. * storage/posix: handle possible case of double free CID: 1398628, 1400731, 1400732, 1400756, 1124796, 1325526 updates: bz#789278 Change-Id: Ieeaca890288bc4686355f6565f853dc8911344e8 Signed-off-by: Amar Tumballi <amarts@redhat.com> Signed-off-by: Sheetal Pamecha <spamecha@redhat.com>
* Fix some "Null pointer dereference" coverity issuesXavi Hernandez2019-05-261-1/+6
| | | | | | | | | | | | | | | | | | | | | | This patch fixes the following CID's: * 1124829 * 1274075 * 1274083 * 1274128 * 1274135 * 1274141 * 1274143 * 1274197 * 1274205 * 1274210 * 1274211 * 1288801 * 1398629 Change-Id: Ia7c86cfab3245b20777ffa296e1a59748040f558 Updates: bz#789278 Signed-off-by: Xavi Hernandez <xhernandez@redhat.com>
* protocol: remove compound fopAmar Tumballi2019-04-294-2851/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | Compound fops are kept on wire as a backward compatibility with older AFR modules. The AFR module used beyond 4.x releases are not using compound fops. Hence removing the compound fop in the protocol code. Note that, compound-fops was already an 'option' in AFR, and completely removed since 4.1.x releases. So, point to note is, with this change, we have 2 ways to upgrade when clients of 3.x series are present. i) set 'use-compound-fops' option to 'false' on any volume which is of replica type. And then upgrade the servers. ii) Do a two step upgrade. First from current version (which will already be EOL if it's using compound) to a 4.1..6.x version, and then an upgrade to 7.x. Consider the overall code which we are removing for the option seems quite high, I believe it is worth it. updates: bz#1693692 Signed-off-by: Amar Tumballi <amarts@redhat.com> Change-Id: I0a8876d0367a15e1410ec845f251d5d3097ee593
* Replace memdup() with gf_memdup()Vijay Bellur2019-04-121-1/+1
| | | | | | | | | memdup() and gf_memdup() have the same implementation. Removed one API as the presence of both can be confusing. Change-Id: I562130c668457e13e4288e592792872d2e49887e updates: bz#1193929 Signed-off-by: Vijay Bellur <vbellur@redhat.com>
* client/fini: return fini after rpc cleanupMohammed Rafi KC2019-04-112-6/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | There is a race condition in rpc_transport later and client fini. Sequence of events to happen the race condition 1) When we want to destroy a graph, we send a parent down event first 2) Once parent down received on a client xlator, we will initiates a rpc disconnect 3) This will in turn generates a child down event. 4) When we process child down, we first do fini for Every xlator 5) On successful return of fini, we delete the graph Here after the step 5, there is a chance that the fini on client might not be finished. Because an rpc_tranpsort ref can race with the above sequence. So we have to wait till all rpc's are successfully freed before returning the fini from client Change-Id: I20145662d71fb837e448a4d3210d1fcb2855f2d4 fixes: bz#1659708 Signed-off-by: Mohammed Rafi KC <rkavunga@redhat.com>
* protocol: add an option to force using old-protocolAmar Tumballi2019-04-103-3/+24
| | | | | | | | | | | | | | As protocol implements every fop, and in general a large part of the codebase. Considering our regression is run mostly in 1 machine, there was no way of forcing the client to use old protocol (while new one is available). With this patch, a new 'testing' option is provided which forces client to use old protocol if found. This should help increase the code coverage by at least 10k lines overall. updates: bz#1693692 Change-Id: Ie45256f7dea250671b689c72b4b6f25037cef948 Signed-off-by: Amar Tumballi <amarts@redhat.com>
* mgmt/shd: Implement multiplexing in self heal daemonMohammed Rafi KC2019-04-011-1/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Problem: Shd daemon is per node, which means they create a graph with all volumes on it. While this is a great for utilizing resources, it is so good in terms of performance and managebility. Because self-heal daemons doesn't have capability to automatically reconfigure their graphs. So each time when any configurations changes happens to the volumes(replicate/disperse), we need to restart shd to bring the changes into the graph. Because of this all on going heal for all other volumes has to be stopped in the middle, and need to restart all over again. Solution: This changes makes shd as a per volume daemon, so that the graph will be generated for each volumes. When we want to start/reconfigure shd for a volume, we first search for an existing shd running on the node, if there is none, we will start a new process. If already a daemon is running for shd, then we will simply detach a graph for a volume and reatach the updated graph for the volume. This won't touch any of the on going operations for any other volumes on the shd daemon. Example of an shd graph when it is per volume graph ----------------------- | debug-iostat | ----------------------- / | \ / | \ --------- --------- ---------- | AFR-1 | | AFR-2 | | AFR-3 | -------- --------- ---------- A running shd daemon with 3 volumes will be like--> graph ----------------------- | debug-iostat | ----------------------- / | \ / | \ ------------ ------------ ------------ | volume-1 | | volume-2 | | volume-3 | ------------ ------------ ------------ Change-Id: Idcb2698be3eeb95beaac47125565c93370afbd99 fixes: bz#1659708 Signed-off-by: Mohammed Rafi KC <rkavunga@redhat.com>
* protocol/client: Do not fallback to anon-fd if fd is not openPranith Kumar K2019-03-311-1/+7
| | | | | | | | | | | | | | | | | | If an open comes on a file when a brick is down and after the brick comes up, a fop comes on the fd, client xlator would still wind the fop on anon-fd leading to wrong behavior of the fops in some cases. Example: If lk fop is issued on the fd just after the brick is up in the scenario above, lk fop will be sent on anon-fd instead of failing it on that client xlator. This lock will never be freed upon close of the fd as flush on anon-fd is invalid and is not wound below server xlator. As a fix, failing the fop unless the fd has FALLBACK_TO_ANON_FD flag. Change-Id: I77692d056660b2858e323bdabdfe0a381807cccc fixes bz#1390914 Signed-off-by: Pranith Kumar K <pkarampu@redhat.com>
* client-rpc: Fix the payload being sent on the wirePoornima G2019-03-296-244/+308
| | | | | | | | | | | | | | | | | | | The fops allocate 3 kind of payload(buffer) in the client xlator: - fop payload, this is the buffer allocated by the write and put fop - rsphdr paylod, this is the buffer required by the reply cbk of some fops like lookup, readdir. - rsp_paylod, this is the buffer required by the reply cbk of fops like readv etc. Currently, in the lookup and readdir fop the rsphdr is sent as payload, hence the allocated rsphdr buffer is also sent on the wire, increasing the bandwidth consumption on the wire. With this patch, the issue is fixed. Fixes: bz#1692093 Change-Id: Ie8158921f4db319e60ad5f52d851fa5c9d4a269b Signed-off-by: Poornima G <pgurusid@redhat.com>
* clang: Fix various missing checks for empty listShyamsundarR2018-12-141-4/+6
| | | | | | | | | | | | | | | | | | | | When using list_for_each_entry(_safe) functions, care needs to be taken that the list passed in are not empty, as these functions are not empty list safe. clag scan reported various points where this this pattern could be caught, and this patch fixes the same. Additionally the following changes are present in this patch, - Added an explicit op_ret setting in error case in the macro MAKE_INODE_HANDLE to address another clang issue reported - Minor refactoring of some functions in quota code, to address possible allocation failures in certain functions (which in turn cause possible empty lists to be passed around) Change-Id: I1e761a8d218708f714effb56fa643df2a3ea2cc7 Updates: bz#1622665 Signed-off-by: ShyamsundarR <srangana@redhat.com>
* copy_file_range support in GlusterFSRaghavendra Bhat2018-12-126-0/+265
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * libglusterfs changes to add new fop * Fuse changes: - Changes in fuse bridge xlator to receive and send responses * posix changes to perform the op on the backend filesystem * protocol and rpc changes for sending and receiving the fop * gfapi changes for performing the fop * tools: glfs-copy-file-range tool for testing copy_file_range fop - Although, copy_file_range support has been added to the upstream fuse kernel module, no release has been made yet of a kernel which contains the support. It is expected to come in the upcoming release of linux-4.20 So, as of now, executing copy_file_range fop on a fused based filesystem results in fuse kernel module sending read on the source fd and write on the destination fd. Therefore a small gfapi based tool has been written to be able test the copy_file_range fop. This tool is similar (in functionality) to the example program given in copy_file_range man page. So, running regular copy_file_range on a fuse mount point and running gfapi based glfs-copy-file-range tool gives some idea about how fast, the copy_file_range (or reflink) can be. On the local machine this was the result obtained. mount -t glusterfs workstation:new /mnt/glusterfs [root@workstation ~]# cd /mnt/glusterfs/ [root@workstation glusterfs]# ls file [root@workstation glusterfs]# cd [root@workstation ~]# time /tmp/a.out /mnt/glusterfs/file /mnt/glusterfs/new real 0m6.495s user 0m0.000s sys 0m1.439s [root@workstation ~]# time glfs-copy-file-range $(hostname) new /tmp/glfs.log /file /rrr OPEN_SRC: opening /file is success OPEN_DST: opening /rrr is success FSTAT_SRC: fstat on /rrr is success copy_file_range successful real 0m0.309s user 0m0.039s sys 0m0.017s This tool needs following arguments 1) hostname 2) volume name 3) log file path 4) source file path (relative to the gluster volume root) 5) destination file path (relative to the gluster volume root) "glfs-copy-file-range <hostname> <volume> <log file path> <source> <destination>" - Added a testcase as well to run glfs-copy-file-range tool * io-stats changes to capture the fop for profiling * NOTE: - Added conditional check to see whether the copy_file_range syscall is available or not. If not, then return ENOSYS. - Added conditional check for kernel minor version in fuse_kernel.h and fuse-bridge while referring to copy_file_range. And the kernel minor version is kept as it is. i.e. 24. Increment it in future when there is a kernel release which contains the support for copy_file_range fop in fuse kernel module. * The document which contains a writeup on this enhancement can be found at https://docs.google.com/document/d/1BSILbXr_knynNwxSyyu503JoTz5QFM_4suNIh2WwrSc/edit Change-Id: I280069c814dd21ce6ec3be00a884fc24ab692367 updates: #536 Signed-off-by: Raghavendra Bhat <raghavendra@redhat.com>
* all: add xlator_api to many translatorsAmar Tumballi2018-12-061-0/+15
| | | | | | Fixes: #164 Change-Id: I93ad6f0232a1dc534df099059f69951e1339086f Signed-off-by: Amar Tumballi <amarts@redhat.com>
* libglusterfs: Move devel headers under glusterfs directoryShyamsundarR2018-12-0512-36/+36
| | | | | | | | | | | | | | | | | | | | | | | | libglusterfs devel package headers are referenced in code using include semantics for a program, this while it works can be better especially when dealing with out of tree xlator builds or in general out of tree devel package usage. Towards this, the following changes are done, - moved all devel headers under a glusterfs directory - Included these headers using system header notation <> in all code outside of libglusterfs - Included these headers using own program notation "" within libglusterfs This change although big, is just moving around the headers and making it correct when including these headers from other sources. This helps us correctly include libglusterfs includes without namespace conflicts. Change-Id: Id2a98854e671a7ee5d73be44da5ba1a74252423b Updates: bz#1193929 Signed-off-by: ShyamsundarR <srangana@redhat.com>
* Multiple xlator .h files: remove unused private gf_* memory types.Yaniv Kaul2018-11-301-1/+0
| | | | | | | | | | | | | It seems there were quite a few unused enums (that in turn cause unndeeded memory allocation) in some xlators. I've removed them, hopefully not causing any damage. Compile-tested only! updates: bz#1193929 Signed-off-by: Yaniv Kaul <ykaul@redhat.com> Change-Id: I8252bd763dc1506e2d922496d896cd2fc0886ea7
* core: create a constant for default network timeoutXavi Hernandez2018-11-231-1/+1
| | | | | | | | | | A new constant named GF_NETWORK_TIMEOUT has been defined and all references to the hard-coded timeout of 42 seconds have been replaced with this constant. Change-Id: Id30f5ce4f1230f9288d9e300538624bcf1a6da27 fixes: bz#1652852 Signed-off-by: Xavi Hernandez <xhernandez@redhat.com>
* protocol/client: unchecked return valueShwetha Acharya2018-11-201-1/+6
| | | | | | | | | | | | | | Problem: In client_process_response_v2, value returned from function client_post_common_dict is not checked for errors before being used. Solution: Added a check condition to resolve the issue. CID: 1390020 Change-Id: I4d297f33c8dd332ae5f6f21667a4871133b2b570 updates: bz#789278 Signed-off-by: Shwetha Acharya <sacharya@redhat.com>
* all: fix the format string exceptionsAmar Tumballi2018-11-051-2/+2
| | | | | | | | | | | | | | | | Currently, there are possibilities in few places, where a user-controlled (like filename, program parameter etc) string can be passed as 'fmt' for printf(), which can lead to segfault, if the user's string contains '%s', '%d' in it. While fixing it, makes sense to make the explicit check for such issues across the codebase, by making the format call properly. Fixes: CVE-2018-14661 Fixes: bz#1644763 Change-Id: Ib547293f2d9eb618594cbff0df3b9c800e88bde4 Signed-off-by: Amar Tumballi <amarts@redhat.com>
* protocol: remove the option 'verify-volfile-checksum'Amar Tumballi2018-11-051-84/+1
| | | | | | | | | | | | | | | | 'getspec' operation is not used between 'client' and 'server' ever since we have off-loaded volfile management to glusterd, ie, at least 7 years. No reason to keep the dead code! The removed option had no meaning, as glusterd didn't provide a way to set (or unset) this option. So, no regression should be observed from any of the existing glusterfs deployment, supported or unsupported. Updates: CVE-2018-14653 Updates: bz#1644756 Change-Id: I4a2e0f673c5bcd4644976a61dbd2d37003a428eb Signed-off-by: Amar Tumballi <amarts@redhat.com>
* Land part 2 of clang-format changesGluster Ant2018-09-128-19701/+19598
| | | | | Change-Id: Ia84cc24c8924e6d22d02ac15f611c10e26db99b4 Signed-off-by: Nigel Babu <nigelb@redhat.com>
* Land clang-format changesGluster Ant2018-09-124-789/+733
| | | | Change-Id: I6f5d8140a06f3c1b2d196849299f8d483028d33b
* Multiple files: calloc -> mallocYaniv Kaul2018-09-041-21/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | xlators/storage/posix/src/posix-inode-fd-ops.c: xlators/storage/posix/src/posix-helpers.c: xlators/storage/bd/src/bd.c: xlators/protocol/client/src/client-lk.c: xlators/performance/quick-read/src/quick-read.c: xlators/performance/io-cache/src/page.c xlators/nfs/server/src/nfs3-helpers.c xlators/nfs/server/src/nfs-fops.c xlators/nfs/server/src/mount3udp_svc.c xlators/nfs/server/src/mount3.c xlators/mount/fuse/src/fuse-helpers.c xlators/mount/fuse/src/fuse-bridge.c xlators/mgmt/glusterd/src/glusterd-utils.c xlators/mgmt/glusterd/src/glusterd-syncop.h xlators/mgmt/glusterd/src/glusterd-snapshot.c xlators/mgmt/glusterd/src/glusterd-rpc-ops.c xlators/mgmt/glusterd/src/glusterd-replace-brick.c xlators/mgmt/glusterd/src/glusterd-op-sm.c xlators/mgmt/glusterd/src/glusterd-mgmt.c xlators/meta/src/subvolumes-dir.c xlators/meta/src/graph-dir.c xlators/features/trash/src/trash.c xlators/features/shard/src/shard.h xlators/features/shard/src/shard.c xlators/features/marker/src/marker-quota.c xlators/features/locks/src/common.c xlators/features/leases/src/leases-internal.c xlators/features/gfid-access/src/gfid-access.c xlators/features/cloudsync/src/cloudsync-plugins/src/cloudsyncs3/src/libcloudsyncs3.c xlators/features/bit-rot/src/bitd/bit-rot.c xlators/features/bit-rot/src/bitd/bit-rot-scrub.c bxlators/encryption/crypt/src/metadata.c xlators/encryption/crypt/src/crypt.c xlators/performance/md-cache/src/md-cache.c: Move to GF_MALLOC() instead of GF_CALLOC() when possible It doesn't make sense to calloc (allocate and clear) memory when the code right away fills that memory with data. It may be optimized by the compiler, or have a microscopic performance improvement. In some cases, also changed allocation size to be sizeof some struct or type instead of a pointer - easier to read. In some cases, removed redundant strlen() calls by saving the result into a variable. 1. Only done for the straightforward cases. There's room for improvement. 2. Please review carefully, especially for string allocation, with the terminating NULL string. Only compile-tested! .. and allocate memory as much as needed. xlators/nfs/server/src/mount3.c : Don't blindly allocate PATH_MAX, but strlen() the string and allocate appropriately. Also, align error messges. updates: bz#1193929 Original-Author: Yaniv Kaul <ykaul@redhat.com> Signed-off-by: Yaniv Kaul <ykaul@redhat.com> Signed-off-by: Yaniv Kaul <ykaul@redhat.com> Change-Id: Ibda6f33dd180b7f7694f20a12af1e9576fe197f5
* protocol: coverity fixesBhumika Goyal2018-08-222-8/+4
| | | | | | | | Fixes CID: 1389388 1389320 1274113 1388881 1388623 1124801 1124795 Change-Id: Ia72abc0560c959b0298f42e25abdfc5523755569 updates: bz#789278 Signed-off-by: Bhumika Goyal <bgoyal@redhat.com>
* xlators: protocol: Fix deferencing pointer after free coverity issuesBhumika Goyal2018-08-213-32/+24
| | | | | | | | | | | | | | | | | | | | | | | | | | | The pointer of type struct iobuf * is getting dereferenced after getting freed by iobuf_unref function. Therefore, move this function after all the dereferences of this pointer type. Also, it is useful coding standard to have iobuf_unref just after iobref_add. So, move iobref_add too. Occurences found using Coccinelle script: @@ identifier rsphdr_iobuf; expression E; identifier func; @@ *iobuf_unref(rsphdr_iobuf); ... *E = func(rsphdr_iobuf); Fixes CID: 1390517, 1390278, 1388666, 1356588, 1356587 at [1]. and also some more occurences which were found using the above script but not caught by Coverity. [1]. https://scan6.coverity.com/reports.htm#v42388/p10714/fileInstanceId=84384920&defectInstanceId=25600709&mergedDefectId=1388666 Change-Id: I579e9d12698f14e9e24bc926c6efef16bac5c06c updates: bz#789278 Signed-off-by: Bhumika Goyal <bgoyal@redhat.com>
* build: rename event.h to gf-event.hNiels de Vos2018-07-271-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | Newer FreeBSD versions (noticed with 10.3-RELEASE) provide a event.h file that on occasion gets included instead of the libglusterfs file. When this happens, 'struct event_pool' will not be defined and building will fail with errors like: autoscale-threads.c:18:55: error: incomplete definition of type 'struct event_pool' int thread_count = pool->eventthreadcount; ~~~~^ autoscale-threads.c:17:16: note: forward declaration of 'struct event_pool' struct event_pool *pool = ctx->event_pool; ^ This problem is caused by 'pkg-config --cflags uuid' that adds /usr/local/include to the GF_CPPFLAGS. The use of libuuid is preferred so that the contrib/uuid/ directory can be removed. By renaming event.h to gf-event.h there is no conflict between the different event.h files anymore and compiling on FreeBSD works without issues. Change-Id: Ie69f6b8a4f8f8e9630d39a86693eb74674f0f763 Updates: bz#1607319 Signed-off-by: Niels de Vos <ndevos@redhat.com>
* All: run codespell on the code and fix issues.Yaniv Kaul2018-07-221-1/+1
| | | | | | | | | | | | Please review, it's not always just the comments that were fixed. I've had to revert of course all calls to creat() that were changed to create() ... Only compile-tested! Change-Id: I7d02e82d9766e272a7fd9cc68e51901d69e5aab5 updates: bz#1193929 Signed-off-by: Yaniv Kaul <ykaul@redhat.com>
* protocol/client: handle the fdctx_destroy properly with different versionsAmar Tumballi2018-07-052-74/+133
| | | | | | | | while adding the new version of RPC, this part was not handled properly Updates: bz#1193929 Change-Id: If4cc4c2db075221b9ed731bacb7cc035f7007c5b Signed-off-by: Amar Tumballi <amarts@redhat.com>
9' href='#n2539'>2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562 3563 3564 3565 3566 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612
/*
   SSSD memberof module

   Copyright (C) Simo Sorce <idra@samba.org> 2008

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <string.h>
#include "ldb_module.h"
#include "util/util.h"
#include "dhash.h"

#define DB_MEMBER "member"
#define DB_MEMBEROF "memberof"
#define DB_MEMBERUID "memberuid"
#define DB_NAME "name"
#define DB_USER_CLASS "user"
#define DB_OC "objectClass"

#ifndef talloc_zfree
#define talloc_zfree(ptr) do { talloc_free(ptr); ptr = NULL; } while(0)
#endif

#ifndef MAX
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#endif

struct mbof_dn_array {
    struct ldb_dn **dns;
    int num;
};

struct mbof_dn {
    struct mbof_dn *next;
    struct ldb_dn *dn;
};

struct mbof_ctx {
    struct ldb_module *module;
    struct ldb_request *req;

    struct ldb_control **ret_ctrls;
    struct ldb_extended *ret_resp;
};

struct mbof_add_operation {
    struct mbof_add_ctx *add_ctx;
    struct mbof_add_operation *next;

    struct mbof_dn_array *parents;
    struct ldb_dn *entry_dn;

    struct ldb_message *entry;
};

struct mbof_memberuid_op {
    struct ldb_dn *dn;
    struct ldb_message_element *el;
};

struct mbof_add_ctx {
    struct mbof_ctx *ctx;

    struct mbof_add_operation *add_list;
    struct mbof_add_operation *current_op;

    struct ldb_message *msg;
    struct ldb_dn *msg_dn;
    bool terminate;

    struct mbof_dn *missing;

    struct mbof_memberuid_op *muops;
    int num_muops;
    int cur_muop;
};

struct mbof_del_ancestors_ctx {
    struct mbof_dn_array *new_list;
    int num_direct;
    int cur;

    struct ldb_message *entry;
};

struct mbof_del_operation {
    struct mbof_del_ctx *del_ctx;
    struct mbof_del_operation *parent;
    struct mbof_del_operation **children;
    int num_children;
    int next_child;

    struct ldb_dn *entry_dn;

    struct ldb_message *entry;
    struct ldb_message **parents;
    int num_parents;
    int cur_parent;

    struct mbof_del_ancestors_ctx *anc_ctx;
};

struct mbof_mod_ctx;

struct mbof_del_ctx {
    struct mbof_ctx *ctx;

    struct mbof_del_operation *first;
    struct mbof_dn *history;

    struct ldb_message **mus;
    int num_mus;

    struct mbof_memberuid_op *muops;
    int num_muops;
    int cur_muop;

    struct mbof_mod_ctx *follow_mod;
    bool is_mod;
};

struct mbof_mod_ctx {
    struct mbof_ctx *ctx;

    const struct ldb_message_element *membel;
    struct ldb_message *entry;

    struct mbof_dn_array *to_add;

    struct ldb_message *msg;
    bool terminate;
};

static struct mbof_ctx *mbof_init(struct ldb_module *module,
                                  struct ldb_request *req)
{
    struct mbof_ctx *ctx;

    ctx = talloc_zero(req, struct mbof_ctx);
    if (!ctx) {
        return NULL;
    }

    ctx->module = module;
    ctx->req = req;

    return ctx;
}

static int entry_is_user_object(struct ldb_message *entry)
{
    struct ldb_message_element *el;
    struct ldb_val *val;
    int i;

    el = ldb_msg_find_element(entry, DB_OC);
    if (!el) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    /* see if this is a user */
    for (i = 0; i < el->num_values; i++) {
        val = &(el->values[i]);
        if (strncasecmp(DB_USER_CLASS, (char *)val->data, val->length) == 0) {
            return LDB_SUCCESS;
        }
    }

    return LDB_ERR_NO_SUCH_ATTRIBUTE;
}

static int mbof_append_muop(TALLOC_CTX *memctx,
                            struct mbof_memberuid_op **_muops,
                            int *_num_muops,
                            int flags,
                            struct ldb_dn *parent,
                            const char *name)
{
    struct mbof_memberuid_op *muops = *_muops;
    int num_muops = *_num_muops;
    struct mbof_memberuid_op *op;
    struct ldb_val *val;
    int i;

    op = NULL;
    if (muops) {
        for (i = 0; i < num_muops; i++) {
            if (ldb_dn_compare(parent, muops[i].dn) == 0) {
                op = &muops[i];
                break;
            }
        }
    }
    if (!op) {
        muops = talloc_realloc(memctx, muops,
                               struct mbof_memberuid_op,
                               num_muops + 1);
        if (!muops) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
        op = &muops[num_muops];
        num_muops++;
        *_muops = muops;
        *_num_muops = num_muops;

        op->dn = parent;
        op->el = NULL;
    }

    if (!op->el) {
        op->el = talloc_zero(muops, struct ldb_message_element);
        if (!op->el) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
        op->el->name = talloc_strdup(op->el, DB_MEMBERUID);
        if (!op->el->name) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
        op->el->flags = flags;
    }

    for (i = 0; i < op->el->num_values; i++) {
        if (strcmp((char *)op->el->values[i].data, name) == 0) {
            /* we already have this value, get out*/
            return LDB_SUCCESS;
        }
    }

    val = talloc_realloc(op->el, op->el->values,
                         struct ldb_val, op->el->num_values + 1);
    if (!val) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    val[op->el->num_values].data = (uint8_t *)talloc_strdup(val, name);
    if (!val[op->el->num_values].data) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    val[op->el->num_values].length = strlen(name);

    op->el->values = val;
    op->el->num_values++;

    return LDB_SUCCESS;
}


/* add operation */

/* An add operation is quite simple.
 * First of all a new object cannot yet have parents, so the only memberof
 * attribute that can be added to any member contains just one object DN.
 *
 * The real add operation is done first, to assure nothing else fails.
 * Then we list all members of the object just created, and for each member
 * we create an "add operation" and we pass it a parent list of one member
 * (the object we just added again).
 *
 * For each add operation we lookup the object we want to operate on.
 * We take the list of memberof attributes and sort out which parents are
 * still missing from the parent list we have provided.
 * We modify the object memberof attributes to reflect the new memberships.
 * Then we list all members of this object, and for each once again we create
 * an "add operation" as we did in the initial object.
 *
 * Processing stops when the target object does not have members or when it
 * already has all the parents (can happen if nested groups create loops).
 *
 * Group cache unrolling:
 * Every time we add a memberof attribute to an actual user object,
 * we proceed to store the user name.
 *
 * At the end we will add a memberuid attribute to our new object that
 * includes all direct and indeirect user members names.
 */

static int mbof_append_addop(struct mbof_add_ctx *add_ctx,
                             struct mbof_dn_array *parents,
                             struct ldb_dn *entry_dn)
{
    struct mbof_add_operation *lastop = NULL;
    struct mbof_add_operation *addop;

    /* test if this is a duplicate */
    /* FIXME: this is not efficient */
    if (add_ctx->add_list) {
        do {
            if (lastop) {
                lastop = lastop->next;
            } else {
                lastop = add_ctx->add_list;
            }

            /* FIXME: check if this is right, might have to compare parents */
            if (ldb_dn_compare(lastop->entry_dn, entry_dn) == 0) {
                /* duplicate found */
                return LDB_SUCCESS;
            }
        } while (lastop->next);
    }

    addop = talloc_zero(add_ctx, struct mbof_add_operation);
    if (!addop) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    addop->add_ctx = add_ctx;
    addop->parents = parents;
    addop->entry_dn = entry_dn;

    if (add_ctx->add_list) {
        lastop->next = addop;
    } else {
        add_ctx->add_list = addop;
    }

    return LDB_SUCCESS;
}

static int memberof_recompute_task(struct ldb_module *module,
                                   struct ldb_request *req);

static int mbof_add_callback(struct ldb_request *req,
                             struct ldb_reply *ares);
static int mbof_next_add(struct mbof_add_operation *addop);
static int mbof_next_add_callback(struct ldb_request *req,
                                  struct ldb_reply *ares);
static int mbof_add_operation(struct mbof_add_operation *addop);
static int mbof_add_missing(struct mbof_add_ctx *add_ctx, struct ldb_dn *dn);
static int mbof_add_cleanup(struct mbof_add_ctx *add_ctx);
static int mbof_add_cleanup_callback(struct ldb_request *req,
                                     struct ldb_reply *ares);
static int mbof_add_muop(struct mbof_add_ctx *add_ctx);
static int mbof_add_muop_callback(struct ldb_request *req,
                                  struct ldb_reply *ares);

static int memberof_add(struct ldb_module *module, struct ldb_request *req)
{
    struct ldb_context *ldb = ldb_module_get_ctx(module);
    struct mbof_add_ctx *add_ctx;
    struct mbof_ctx *ctx;
    struct ldb_request *add_req;
    struct ldb_message_element *el;
    struct mbof_dn_array *parents;
    struct ldb_dn *valdn;
    int i, ret;

    if (ldb_dn_is_special(req->op.add.message->dn)) {

        if (strcmp("@MEMBEROF-REBUILD",
                   ldb_dn_get_linearized(req->op.add.message->dn)) == 0) {
            return memberof_recompute_task(module, req);
        }

        /* do not manipulate other control entries */
        return ldb_next_request(module, req);
    }

    /* check if memberof is specified */
    el = ldb_msg_find_element(req->op.add.message, DB_MEMBEROF);
    if (el) {
        ldb_debug(ldb, LDB_DEBUG_ERROR,
                  "Error: the memberof attribute is readonly.");
        return LDB_ERR_UNWILLING_TO_PERFORM;
    }

    /* check if memberuid is specified */
    el = ldb_msg_find_element(req->op.add.message, DB_MEMBERUID);
    if (el) {
        ldb_debug(ldb, LDB_DEBUG_ERROR,
                  "Error: the memberuid attribute is readonly.");
        return LDB_ERR_UNWILLING_TO_PERFORM;
    }

    ctx = mbof_init(module, req);
    if (!ctx) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    add_ctx = talloc_zero(ctx, struct mbof_add_ctx);
    if (!add_ctx) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    add_ctx->ctx = ctx;

    add_ctx->msg = ldb_msg_copy(add_ctx, req->op.add.message);
    if (!add_ctx->msg) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    add_ctx->msg_dn = add_ctx->msg->dn;

    /* continue with normal ops if there are no members */
    el = ldb_msg_find_element(add_ctx->msg, DB_MEMBER);
    if (!el) {
        add_ctx->terminate = true;
        goto done;
    }

    parents = talloc_zero(add_ctx, struct mbof_dn_array);
    if (!parents) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    parents->dns = talloc_array(parents, struct ldb_dn *, 1);
    if (!parents->dns) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    parents->dns[0] = add_ctx->msg_dn;
    parents->num = 1;

    /* process new members */
    /* check we are not adding ourselves as member as well */
    for (i = 0; i < el->num_values; i++) {
        valdn = ldb_dn_from_ldb_val(add_ctx, ldb, &el->values[i]);
        if (!valdn || !ldb_dn_validate(valdn)) {
            ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid dn value: [%s]",
                                            (const char *)el->values[i].data);
            return LDB_ERR_INVALID_DN_SYNTAX;
        }
        if (ldb_dn_compare(valdn, req->op.add.message->dn) == 0) {
            ldb_debug(ldb, LDB_DEBUG_ERROR,
                      "Adding self as member is not permitted! Skipping");
            continue;
        }
        ret = mbof_append_addop(add_ctx, parents, valdn);
        if (ret != LDB_SUCCESS) {
            return ret;
        }
    }

done:
    /* add original object */
    ret = ldb_build_add_req(&add_req, ldb, add_ctx,
                            add_ctx->msg, req->controls,
                            add_ctx, mbof_add_callback,
                            req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_next_request(module, add_req);
}

static int mbof_add_callback(struct ldb_request *req,
                             struct ldb_reply *ares)
{
    struct mbof_add_ctx *add_ctx;
    struct mbof_ctx *ctx;
    int ret;

    add_ctx = talloc_get_type(req->context, struct mbof_add_ctx);
    ctx = add_ctx->ctx;

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        /* shouldn't happen */
        talloc_zfree(ares);
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        if (add_ctx->terminate) {
            return ldb_module_done(ctx->req,
                                   ctx->ret_ctrls,
                                   ctx->ret_resp,
                                   LDB_SUCCESS);
        }

        if (add_ctx->current_op == NULL) {
            /* first operation */
            ctx->ret_ctrls = talloc_steal(ctx, ares->controls);
            ctx->ret_resp = talloc_steal(ctx, ares->response);
            ret = mbof_next_add(add_ctx->add_list);
        }
        else if (add_ctx->current_op->next) {
            /* next operation */
            ret = mbof_next_add(add_ctx->current_op->next);
        }
        else {
            /* no more operations */
            if (add_ctx->missing) {
                ret = mbof_add_cleanup(add_ctx);
            }
            else if (add_ctx->muops) {
                ret = mbof_add_muop(add_ctx);
            }
            else {
                return ldb_module_done(ctx->req,
                                       ctx->ret_ctrls,
                                       ctx->ret_resp,
                                       LDB_SUCCESS);
            }
        }

        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_next_add(struct mbof_add_operation *addop)
{
    static const char *attrs[] = { DB_OC, DB_NAME,
                                   DB_MEMBER, DB_MEMBEROF, NULL };
    struct ldb_context *ldb;
    struct ldb_request *req;
    struct mbof_add_ctx *add_ctx;
    struct mbof_ctx *ctx;
    int ret;

    add_ctx = addop->add_ctx;
    ctx = add_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    /* mark the operation as being handled */
    add_ctx->current_op = addop;

    ret = ldb_build_search_req(&req, ldb, ctx,
                               addop->entry_dn, LDB_SCOPE_BASE,
                               NULL, attrs, NULL,
                               addop, mbof_next_add_callback,
                               ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_request(ldb, req);
}

static int mbof_next_add_callback(struct ldb_request *req,
                                  struct ldb_reply *ares)
{
    struct mbof_add_operation *addop;
    struct mbof_add_ctx *add_ctx;
    struct ldb_context *ldb;
    struct mbof_ctx *ctx;
    int ret;

    addop = talloc_get_type(req->context, struct mbof_add_operation);
    add_ctx = addop->add_ctx;
    ctx = add_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        if (addop->entry != NULL) {
            ldb_debug(ldb, LDB_DEBUG_TRACE,
                           "Found multiple entries for (%s)",
                           ldb_dn_get_linearized(addop->entry_dn));
            /* more than one entry per dn ?? db corrupted ? */
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        addop->entry = talloc_steal(addop, ares->message);
        if (addop->entry == NULL) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        break;
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        talloc_zfree(ares);
        if (addop->entry == NULL) {
            ldb_debug(ldb, LDB_DEBUG_TRACE, "Entry not found (%s)",
                           ldb_dn_get_linearized(addop->entry_dn));

            /* this target does not exists, save as missing */
            ret = mbof_add_missing(add_ctx, addop->entry_dn);
            if (ret != LDB_SUCCESS) {
                return ldb_module_done(ctx->req, NULL, NULL, ret);
            }
            /* now try the next operation */
            if (add_ctx->current_op->next) {
                ret = mbof_next_add(add_ctx->current_op->next);
            }
            else {
                /* no more operations */
                if (add_ctx->missing) {
                    ret = mbof_add_cleanup(add_ctx);
                }
                else if (add_ctx->muops) {
                    ret = mbof_add_muop(add_ctx);
                }
                else {
                    return ldb_module_done(ctx->req,
                                           ctx->ret_ctrls,
                                           ctx->ret_resp,
                                           LDB_SUCCESS);
                }
            }
            if (ret != LDB_SUCCESS) {
                return ldb_module_done(ctx->req, NULL, NULL, ret);
            }
        }
        else {
            ret = mbof_add_operation(addop);
            if (ret != LDB_SUCCESS) {
                return ldb_module_done(ctx->req, NULL, NULL, ret);
            }
        }
        return LDB_SUCCESS;
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

/* if it is a group, add all members for cascade effect
 * add memberof attribute to this entry
 */
static int mbof_add_operation(struct mbof_add_operation *addop)
{

    TALLOC_CTX *tmp_ctx;
    struct mbof_ctx *ctx;
    struct mbof_add_ctx *add_ctx;
    struct ldb_context *ldb;
    struct ldb_message_element *el;
    struct ldb_request *mod_req;
    struct ldb_message *msg;
    struct ldb_dn *elval_dn;
    struct ldb_dn *valdn;
    struct mbof_dn_array *parents;
    int i, j, ret;
    const char *val;
    const char *name;

    add_ctx = addop->add_ctx;
    ctx = add_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    parents = talloc_zero(add_ctx, struct mbof_dn_array);
    if (!parents) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    /* can't be more than the immediate parent */
    parents->dns = talloc_array(parents, struct ldb_dn *,
                                addop->parents->num);
    if (!parents->dns) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    /* create new parent set for this entry */
    for (i = 0; i < addop->parents->num; i++) {
        /* never add yourself as memberof */
        if (ldb_dn_compare(addop->parents->dns[i], addop->entry_dn) == 0) {
            continue;
        }
        parents->dns[parents->num] = addop->parents->dns[i];
        parents->num++;
    }

    /* remove entries that are already there */
    el = ldb_msg_find_element(addop->entry, DB_MEMBEROF);
    if (el) {

        tmp_ctx = talloc_new(addop);
        if (!tmp_ctx) return LDB_ERR_OPERATIONS_ERROR;

        for (i = 0; i < el->num_values; i++) {
            elval_dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &el->values[i]);
            if (!elval_dn) {
                ldb_debug(ldb, LDB_DEBUG_TRACE, "Invalid DN in memberof [%s]",
                                            (const char *)el->values[i].data);
                talloc_free(tmp_ctx);
                return LDB_ERR_OPERATIONS_ERROR;
            }
            for (j = 0; j < parents->num; j++) {
                if (ldb_dn_compare(parents->dns[j], elval_dn) == 0) {
                    /* duplicate found */
                    break;
                }
            }
            if (j < parents->num) {
                /* remove duplicate */
                for (;j+1 < parents->num; j++) {
                    parents->dns[j] = parents->dns[j+1];
                }
                parents->num--;
            }
        }

        if (parents->num == 0) {
            /* already contains all parents as memberof, skip to next */
            talloc_free(tmp_ctx);
            talloc_free(addop->entry);
            addop->entry = NULL;

            if (addop->next) {
                return mbof_next_add(addop->next);
            }
            else if (add_ctx->muops) {
                return mbof_add_muop(add_ctx);
            }
            else {
                /* that was the last entry, get out */
                return ldb_module_done(ctx->req,
                                       ctx->ret_ctrls,
                                       ctx->ret_resp,
                                       LDB_SUCCESS);
            }
        }
        talloc_free(tmp_ctx);
    }

    /* if it is a group add all members */
    el = ldb_msg_find_element(addop->entry, DB_MEMBER);
    if (el) {
        for (i = 0; i < el->num_values; i++) {
            valdn = ldb_dn_from_ldb_val(add_ctx, ldb, &el->values[i]);
            if (!valdn) {
                ldb_debug(ldb, LDB_DEBUG_TRACE, "Invalid DN in member [%s]",
                                            (const char *)el->values[i].data);
                return LDB_ERR_OPERATIONS_ERROR;
            }
            if (!ldb_dn_validate(valdn)) {
                ldb_debug(ldb, LDB_DEBUG_TRACE,
                               "Invalid DN syntax for member [%s]",
                                            (const char *)el->values[i].data);
                return LDB_ERR_INVALID_DN_SYNTAX;
            }
            ret = mbof_append_addop(add_ctx, parents, valdn);
            if (ret != LDB_SUCCESS) {
                return ret;
            }
        }
    }

    /* check if we need to store memberuid ops for this entry */
    ret = entry_is_user_object(addop->entry);
    switch (ret) {
    case LDB_SUCCESS:
        /* it's a user object  */
        name = ldb_msg_find_attr_as_string(addop->entry, DB_NAME, NULL);
        if (!name) {
            return LDB_ERR_OPERATIONS_ERROR;
        }

        for (i = 0; i < parents->num; i++) {
            ret = mbof_append_muop(add_ctx, &add_ctx->muops,
                                   &add_ctx->num_muops,
                                   LDB_FLAG_MOD_ADD,
                                   parents->dns[i], name);
            if (ret != LDB_SUCCESS) {
                return ret;
            }
        }

        break;

    case LDB_ERR_NO_SUCH_ATTRIBUTE:
        /* it is not a user object, continue */
        break;

    default:
        /* an error occured, return */
        return ret;
    }

    /* we are done with the entry now */
    talloc_free(addop->entry);
    addop->entry = NULL;

    /* add memberof to entry */
    msg = ldb_msg_new(addop);
    if (!msg) return LDB_ERR_OPERATIONS_ERROR;

    msg->dn = addop->entry_dn;

    ret = ldb_msg_add_empty(msg, DB_MEMBEROF, LDB_FLAG_MOD_ADD, &el);
    if (ret != LDB_SUCCESS) {
        return ret;
    }
    el->values = talloc_array(msg, struct ldb_val, parents->num);
    if (!el->values) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    for (i = 0, j = 0; i < parents->num; i++) {
        if (ldb_dn_compare(parents->dns[i], msg->dn) == 0) continue;
        val = ldb_dn_get_linearized(parents->dns[i]);
        el->values[j].length = strlen(val);
        el->values[j].data = (uint8_t *)talloc_strdup(el->values, val);
        if (!el->values[j].data) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
        j++;
    }
    el->num_values = j;

    ret = ldb_build_mod_req(&mod_req, ldb, add_ctx,
                            msg, NULL,
                            add_ctx, mbof_add_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }
    talloc_steal(mod_req, msg);

    return ldb_next_request(ctx->module, mod_req);
}

static int mbof_add_missing(struct mbof_add_ctx *add_ctx, struct ldb_dn *dn)
{
    struct mbof_dn *mdn;

    mdn = talloc(add_ctx, struct mbof_dn);
    if (!mdn) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    mdn->dn = talloc_steal(mdn, dn);

    /* add to the list */
    mdn->next = add_ctx->missing;
    add_ctx->missing = mdn;

    return LDB_SUCCESS;
}

/* remove unexisting members and add memberuid attribute */
static int mbof_add_cleanup(struct mbof_add_ctx *add_ctx)
{
    struct ldb_context *ldb;
    struct ldb_message *msg;
    struct ldb_request *mod_req;
    struct ldb_message_element *el;
    struct mbof_ctx *ctx;
    struct mbof_dn *iter;
    const char *val;
    int ret, i, num;

    ctx = add_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    num = 0;
    for (iter = add_ctx->missing; iter; iter = iter->next) {
        num++;
    }
    if (num == 0) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    msg = ldb_msg_new(add_ctx);
    if (!msg) return LDB_ERR_OPERATIONS_ERROR;

    msg->dn = add_ctx->msg_dn;

    ret = ldb_msg_add_empty(msg, DB_MEMBER, LDB_FLAG_MOD_DELETE, &el);
    if (ret != LDB_SUCCESS) {
        return ret;
    }
    el->values = talloc_array(msg, struct ldb_val, num);
    if (!el->values) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    el->num_values = num;
    for (i = 0, iter = add_ctx->missing; iter; iter = iter->next, i++) {
        val = ldb_dn_get_linearized(iter->dn);
        el->values[i].length = strlen(val);
        el->values[i].data = (uint8_t *)talloc_strdup(el->values, val);
        if (!el->values[i].data) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
    }

    ret = ldb_build_mod_req(&mod_req, ldb, add_ctx,
                            msg, NULL,
                            add_ctx, mbof_add_cleanup_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_next_request(ctx->module, mod_req);
}

static int mbof_add_cleanup_callback(struct ldb_request *req,
                                     struct ldb_reply *ares)
{
    struct mbof_add_ctx *add_ctx;
    struct mbof_ctx *ctx;
    int ret;

    add_ctx = talloc_get_type(req->context, struct mbof_add_ctx);
    ctx = add_ctx->ctx;

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        /* shouldn't happen */
        talloc_zfree(ares);
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        if (add_ctx->muops) {
            ret = mbof_add_muop(add_ctx);
        }
        else {
            return ldb_module_done(ctx->req,
                                   ctx->ret_ctrls,
                                   ctx->ret_resp,
                                   LDB_SUCCESS);
        }

        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

/* add memberuid attributes to parent groups */
static int mbof_add_muop(struct mbof_add_ctx *add_ctx)
{
    struct ldb_context *ldb;
    struct ldb_message *msg;
    struct ldb_request *mod_req;
    struct mbof_ctx *ctx;
    int ret;

    ctx = add_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    msg = ldb_msg_new(add_ctx);
    if (!msg) return LDB_ERR_OPERATIONS_ERROR;

    msg->dn = add_ctx->muops[add_ctx->cur_muop].dn;
    msg->elements = add_ctx->muops[add_ctx->cur_muop].el;
    msg->num_elements = 1;

    ret = ldb_build_mod_req(&mod_req, ldb, add_ctx,
                            msg, NULL,
                            add_ctx, mbof_add_muop_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_next_request(ctx->module, mod_req);
}

static int mbof_add_muop_callback(struct ldb_request *req,
                                  struct ldb_reply *ares)
{
    struct mbof_add_ctx *add_ctx;
    struct mbof_ctx *ctx;
    int ret;

    add_ctx = talloc_get_type(req->context, struct mbof_add_ctx);
    ctx = add_ctx->ctx;

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        /* shouldn't happen */
        talloc_zfree(ares);
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        add_ctx->cur_muop++;
        if (add_ctx->cur_muop < add_ctx->num_muops) {
            ret = mbof_add_muop(add_ctx);
        }
        else {
            return ldb_module_done(ctx->req,
                                   ctx->ret_ctrls,
                                   ctx->ret_resp,
                                   LDB_SUCCESS);
        }

        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}




/* delete operations */

/* The implementation of delete operations is a bit more complex than an add
 * operation. This is because we need to recompute memberships of potentially
 * quite far descendants and we also have to account for loops and how to
 * break them without ending in an endless loop ourselves.
 * The difficulty is in the fact that while the member -> memberof link is
 * direct, memberof -> member is not as membership is transitive.
 *
 * Ok, first of all, contrary to the add operation, a delete operation
 * involves an existing object that may have existing parents. So, first, we
 * search  the object itself to get the original membership lists (member and
 * memberof) for this object, and we also search for any object that has it as
 * one of its members.
 * Once we have the results, we store object and parents and proceed with the
 * original operation to make sure it is valid.
 *
 * Once the original op returns we proceed fixing parents (parents being each
 * object that has the delete operation target object as member), if any.
 *
 * For each parent we retrieved we proceed to delete the member attribute that
 * points to the object we just deleted. Once done for all parents (or if no
 * parents exists), we proceed with the children and descendants.
 *
 * To handle the children we create a first ancestor operation that reflects
 * the delete we just made. We set as parents of this object the parents just
 * retrieved with the first search. Then we create a remove list.
 *
 * The remove list contains all objects in the original memberof list and the
 * object dn itself of the original delete operation target object (the first
 * ancestor).
 *
 * An operation is identified by an object that contains a tree of
 * descendants:
 * The remove list for the children, the immediate parent, and the dn and
 * entry of the object this operation is about.
 *
 * We now proceed with adding a new operation for each original member of the
 * first ancestor.
 *
 * In each operation we must first lookup the target object and each immediate
 * parent (all the objects in the tree that have target as a "member").
 *
 * Then we proceed to calculate the new memberof list that we are going to set
 * on the target object.
 * The new memberof list starts with including all the objects that have the
 * target as their direct member.
 * Finally for each entry in this provisional new memberof list we add all its
 * memberof elements to the new memberof list (taking care of excluding
 * duplicates). This way we are certain all direct and indirect membership are
 * accounted for.
 *
 * At this point we have the final new memberof list for this operation and we
 * can proceed to modify the entry.
 *
 * Once the entry has been modified we proceed again to check if there are any
 * children of this entry (the entry has "member"s).
 * We create a new remove list that is the difference between the original
 * entry memberof list and the new memberof list we just stored back in the
 * object.
 * Then for each member we create a new operation.
 *
 * We continue to process operations until no new operations need to be
 * performed.
 *
 * Ordering is important here, se the mbof_del_get_next() function to
 * understand how we proceed to select which new operation to process.
 *
 * As a final operation remove any memberuid corresponding to a removal of
 * a memberof field from a user entry
 */

static int mbof_del_search_callback(struct ldb_request *req,
                                    struct ldb_reply *ares);
static int mbof_orig_del(struct mbof_del_ctx *ctx);
static int mbof_orig_del_callback(struct ldb_request *req,
                                  struct ldb_reply *ares);
static int mbof_del_cleanup_parents(struct mbof_del_ctx *del_ctx);
static int mbof_del_clean_par_callback(struct ldb_request *req,
                                       struct ldb_reply *ares);
static int mbof_del_cleanup_children(struct mbof_del_ctx *del_ctx);
static int mbof_append_delop(struct mbof_del_operation *parent,
                             struct ldb_dn *entry_dn);
static int mbof_del_execute_op(struct mbof_del_operation *delop);
static int mbof_del_exop_search_callback(struct ldb_request *req,
                                         struct ldb_reply *ares);
static int mbof_del_execute_cont(struct mbof_del_operation *delop);
static int mbof_del_ancestors(struct mbof_del_operation *delop);
static int mbof_del_anc_callback(struct ldb_request *req,
                                 struct ldb_reply *ares);
static int mbof_del_mod_entry(struct mbof_del_operation *delop);
static int mbof_del_mod_callback(struct ldb_request *req,
                                 struct ldb_reply *ares);
static int mbof_del_progeny(struct mbof_del_operation *delop);
static int mbof_del_get_next(struct mbof_del_operation *delop,
                             struct mbof_del_operation **nextop);
static int mbof_del_fill_muop(struct mbof_del_ctx *del_ctx,
                              struct ldb_message *entry);
static int mbof_del_muop(struct mbof_del_ctx *ctx);
static int mbof_del_muop_callback(struct ldb_request *req,
                                  struct ldb_reply *ares);


static int memberof_del(struct ldb_module *module, struct ldb_request *req)
{
    static const char *attrs[] = { DB_OC, DB_NAME,
                                   DB_MEMBER, DB_MEMBEROF, NULL };
    struct ldb_context *ldb = ldb_module_get_ctx(module);
    struct mbof_del_operation *first;
    struct ldb_request *search;
    char *expression;
    const char *dn;
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    int ret;

    if (ldb_dn_is_special(req->op.del.dn)) {
        /* do not manipulate our control entries */
        return ldb_next_request(module, req);
    }

    ctx = mbof_init(module, req);
    if (!ctx) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    del_ctx = talloc_zero(ctx, struct mbof_del_ctx);
    if (!del_ctx) {
        talloc_free(ctx);
        return LDB_ERR_OPERATIONS_ERROR;
    }
    del_ctx->ctx = ctx;

    /* create first entry */
    /* the first entry is the parent of all entries and the one where we remove
     * member from, it does not get the same treatment as others */
    first = talloc_zero(del_ctx, struct mbof_del_operation);
    if (!first) {
        talloc_free(ctx);
        return LDB_ERR_OPERATIONS_ERROR;
    }
    del_ctx->first = first;

    first->del_ctx = del_ctx;
    first->entry_dn = req->op.del.dn;

    dn = ldb_dn_get_linearized(req->op.del.dn);
    if (!dn) {
        talloc_free(ctx);
        return LDB_ERR_OPERATIONS_ERROR;
    }
    expression = talloc_asprintf(del_ctx,
                                 "(|(distinguishedName=%s)(%s=%s))",
                                 dn, DB_MEMBER, dn);
    if (!expression) {
        talloc_free(ctx);
        return LDB_ERR_OPERATIONS_ERROR;
    }

    ret = ldb_build_search_req(&search, ldb, del_ctx,
                               NULL, LDB_SCOPE_SUBTREE,
                               expression, attrs, NULL,
                               first, mbof_del_search_callback,
                               req);
    if (ret != LDB_SUCCESS) {
        talloc_free(ctx);
        return ret;
    }

    return ldb_request(ldb, search);
}

static int mbof_del_search_callback(struct ldb_request *req,
                                    struct ldb_reply *ares)
{
    struct mbof_del_operation *first;
    struct ldb_context *ldb;
    struct ldb_message *msg;
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    int ret;

    first = talloc_get_type(req->context, struct mbof_del_operation);
    del_ctx = first->del_ctx;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        msg = ares->message;

        if (ldb_dn_compare(msg->dn, ctx->req->op.del.dn) == 0) {

            if (first->entry != NULL) {
                /* more than one entry per dn ?? db corrupted ? */
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }

            first->entry = talloc_steal(first, msg);
            if (first->entry == NULL) {
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }
        } else {
            first->parents = talloc_realloc(first, first->parents,
                                             struct ldb_message *,
                                             first->num_parents + 1);
            if (!first->parents) {
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }
            msg = talloc_steal(first->parents, ares->message);
            if (!msg) {
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }
            first->parents[first->num_parents] = msg;
            first->num_parents++;
        }
        break;
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        if (first->entry == NULL) {
            /* this target does not exists, too bad! */
            ldb_debug(ldb, LDB_DEBUG_TRACE,
                           "Target entry (%s) not found",
                           ldb_dn_get_linearized(first->entry_dn));
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_NO_SUCH_OBJECT);
        }

        /* now perform the requested delete, before proceeding further */
        ret =  mbof_orig_del(del_ctx);
        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_orig_del(struct mbof_del_ctx *del_ctx)
{
    struct ldb_request *del_req;
    struct mbof_ctx *ctx;
    int ret;

    ctx = del_ctx->ctx;

    ret = ldb_build_del_req(&del_req, ldb_module_get_ctx(ctx->module),
                            ctx->req, ctx->req->op.del.dn, NULL,
                            del_ctx, mbof_orig_del_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_next_request(ctx->module, del_req);
}

static int mbof_orig_del_callback(struct ldb_request *req,
                                  struct ldb_reply *ares)
{
    struct ldb_context *ldb;
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    int ret;

    del_ctx = talloc_get_type(req->context, struct mbof_del_ctx);
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    if (ares->type != LDB_REPLY_DONE) {
        talloc_zfree(ares);
        ldb_set_errstring(ldb, "Invalid reply type!");
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }

    /* save real call stuff */
    ctx->ret_ctrls = talloc_steal(ctx, ares->controls);
    ctx->ret_resp = talloc_steal(ctx, ares->response);

    /* prep following clean ops */
    if (del_ctx->first->num_parents) {

        /* if there are parents there may be memberuids to remove */
        ret = mbof_del_fill_muop(del_ctx, del_ctx->first->entry);
        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }

        /* if there are any parents, fire a removal sequence */
        ret = mbof_del_cleanup_parents(del_ctx);
    }
    else if (ldb_msg_find_element(del_ctx->first->entry, DB_MEMBER)) {
        /* if there are any children, fire a removal sequence */
        ret = mbof_del_cleanup_children(del_ctx);
    }
    /* see if there are memberuid operations to perform */
    else if (del_ctx->muops) {
        return mbof_del_muop(del_ctx);
    }
    else {
        /* no parents nor children, end ops */
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               LDB_SUCCESS);
    }
    if (ret != LDB_SUCCESS) {
        talloc_zfree(ares);
        return ldb_module_done(ctx->req, NULL, NULL, ret);
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_del_cleanup_parents(struct mbof_del_ctx *del_ctx)
{
    struct mbof_del_operation *first;
    struct mbof_ctx *ctx;
    struct ldb_context *ldb;
    struct ldb_request *mod_req;
    struct ldb_message *msg;
    struct ldb_message_element *el;
    const char *val;
    int ret;

    first = del_ctx->first;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    msg = ldb_msg_new(first->parents);
    if (!msg) return LDB_ERR_OPERATIONS_ERROR;

    msg->dn = first->parents[first->cur_parent]->dn;
    first->cur_parent++;

    ret = ldb_msg_add_empty(msg, DB_MEMBER, LDB_FLAG_MOD_DELETE, &el);
    if (ret != LDB_SUCCESS) {
        return ret;
    }
    el->values = talloc_array(msg, struct ldb_val, 1);
    if (!el->values) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    val = ldb_dn_get_linearized(first->entry_dn);
    el->values[0].length = strlen(val);
    el->values[0].data = (uint8_t *)talloc_strdup(el->values, val);
    if (!el->values[0].data) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    el->num_values = 1;

    ret = ldb_build_mod_req(&mod_req, ldb, first->parents,
                            msg, NULL,
                            del_ctx, mbof_del_clean_par_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_next_request(ctx->module, mod_req);
}

static int mbof_del_clean_par_callback(struct ldb_request *req,
                                       struct ldb_reply *ares)
{
    struct mbof_del_operation *first;
    struct ldb_context *ldb;
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    int ret;

    del_ctx = talloc_get_type(req->context, struct mbof_del_ctx);
    first = del_ctx->first;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }

    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    if (ares->type != LDB_REPLY_DONE) {
        talloc_zfree(ares);
        ldb_set_errstring(ldb, "Invalid reply type!");
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }

    if (first->num_parents > first->cur_parent) {
        /* still parents to cleanup, go on */
        ret = mbof_del_cleanup_parents(del_ctx);
    }
    else {
        /* continue */
        if (ldb_msg_find_element(first->entry, DB_MEMBER)) {
            /* if there are any children, fire a removal sequence */
            ret = mbof_del_cleanup_children(del_ctx);
        }
        /* see if there are memberuid operations to perform */
        else if (del_ctx->muops) {
            return mbof_del_muop(del_ctx);
        }
        else {
            /* no children, end ops */
            return ldb_module_done(ctx->req,
                                   ctx->ret_ctrls,
                                   ctx->ret_resp,
                                   LDB_SUCCESS);
        }
    }

    if (ret != LDB_SUCCESS) {
        talloc_zfree(ares);
        return ldb_module_done(ctx->req, NULL, NULL, ret);
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_del_cleanup_children(struct mbof_del_ctx *del_ctx)
{
    struct mbof_del_operation *first;
    struct mbof_ctx *ctx;
    struct ldb_context *ldb;
    const struct ldb_message_element *el;
    struct ldb_dn *valdn;
    int i, ret;

    first = del_ctx->first;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    el = ldb_msg_find_element(first->entry, DB_MEMBER);

    /* prepare del sets */
    for (i = 0; i < el->num_values; i++) {
        valdn = ldb_dn_from_ldb_val(first, ldb, &el->values[i]);
        if (!valdn || !ldb_dn_validate(valdn)) {
            ldb_debug(ldb, LDB_DEBUG_TRACE,
                           "Invalid dn syntax for member [%s]",
                                        (const char *)el->values[i].data);
            return LDB_ERR_INVALID_DN_SYNTAX;
        }
        ret = mbof_append_delop(first, valdn);
        if (ret != LDB_SUCCESS) {
            return ret;
        }
    }

    /* now that sets are built, start processing */
    return mbof_del_execute_op(first->children[0]);
}

static int mbof_append_delop(struct mbof_del_operation *parent,
                             struct ldb_dn *entry_dn)
{
    struct mbof_del_operation *delop;

    delop = talloc_zero(parent, struct mbof_del_operation);
    if (!delop) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    delop->del_ctx = parent->del_ctx;
    delop->parent = parent;
    delop->entry_dn = entry_dn;

    parent->children = talloc_realloc(parent, parent->children,
                                      struct mbof_del_operation *,
                                      parent->num_children +1);
    if (!parent->children) {
        talloc_free(delop);
        return LDB_ERR_OPERATIONS_ERROR;
    }

    parent->children[parent->num_children] = delop;
    parent->num_children++;

    return LDB_SUCCESS;
}

static int mbof_del_execute_op(struct mbof_del_operation *delop)
{
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    struct ldb_context *ldb;
    struct ldb_request *search;
    char *expression;
    const char *dn;
    static const char *attrs[] = { DB_OC, DB_NAME,
                                   DB_MEMBER, DB_MEMBEROF, NULL };
    int ret;

    del_ctx = delop->del_ctx;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    /* load entry */
    dn = ldb_dn_get_linearized(delop->entry_dn);
    if (!dn) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    expression = talloc_asprintf(del_ctx,
                                 "(|(distinguishedName=%s)(%s=%s))",
                                 dn, DB_MEMBER, dn);
    if (!expression) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    ret = ldb_build_search_req(&search, ldb, delop,
                               NULL, LDB_SCOPE_SUBTREE,
                               expression, attrs, NULL,
                               delop, mbof_del_exop_search_callback,
                               ctx->req);
    if (ret != LDB_SUCCESS) {
        talloc_free(ctx);
        return ret;
    }

    return ldb_request(ldb, search);
}

static int mbof_del_exop_search_callback(struct ldb_request *req,
                                         struct ldb_reply *ares)
{
    struct mbof_del_operation *delop;
    struct mbof_del_ctx *del_ctx;
    struct ldb_context *ldb;
    struct mbof_ctx *ctx;
    struct ldb_message *msg;
    int ret;

    delop = talloc_get_type(req->context, struct mbof_del_operation);
    del_ctx = delop->del_ctx;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        msg = ares->message;

        if (ldb_dn_compare(msg->dn, delop->entry_dn) == 0) {

            if (delop->entry != NULL) {
                ldb_debug(ldb, LDB_DEBUG_TRACE,
                               "Found multiple entries for (%s)",
                               ldb_dn_get_linearized(delop->entry_dn));
                /* more than one entry per dn ?? db corrupted ? */
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }

            delop->entry = talloc_steal(delop, msg);
            if (delop->entry == NULL) {
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }
        } else {
            delop->parents = talloc_realloc(delop, delop->parents,
                                            struct ldb_message *,
                                            delop->num_parents + 1);
            if (!delop->parents) {
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }
            msg = talloc_steal(delop->parents, msg);
            if (!msg) {
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }
            delop->parents[delop->num_parents] = msg;
            delop->num_parents++;
        }
        break;
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        if (delop->entry == NULL) {
            /* no target, no party! */
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        /* ok process the entry */
        ret = mbof_del_execute_cont(delop);

        if (ret != LDB_SUCCESS) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_del_execute_cont(struct mbof_del_operation *delop)
{
    struct mbof_del_ancestors_ctx *anc_ctx;
    struct mbof_del_operation *parent;
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    struct ldb_context *ldb;
    struct mbof_dn_array *new_list;
    int i;

    del_ctx = delop->del_ctx;
    parent = delop->parent;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    anc_ctx = talloc_zero(delop, struct mbof_del_ancestors_ctx);
    if (!anc_ctx) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    delop->anc_ctx = anc_ctx;

    new_list = talloc_zero(anc_ctx, struct mbof_dn_array);
    if (!new_list) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    /* at the very least we have a number of memberof elements
     * equal to the number of objects that have this entry as
     * direct member */
    new_list->num = delop->num_parents;

    /* attach the list to the operation */
    delop->anc_ctx->new_list = new_list;
    delop->anc_ctx->num_direct = new_list->num;

    /* do we have any direct parent at all ? */
    if (new_list->num == 0) {
        /* no entries at all, entry ended up being orphaned */
        /* skip to directly set the new memberof list for this entry */

        return mbof_del_mod_entry(delop);
    }

    /* fill in the list if we have parents */
    new_list->dns = talloc_zero_array(new_list,
                                      struct ldb_dn *,
                                      new_list->num);
    if (!new_list->dns) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    for (i = 0; i < delop->num_parents; i++) {
        new_list->dns[i] = delop->parents[i]->dn;
    }

    /* before proceeding we also need to fetch the ancestors (anew as some may
     * have changed by preceeding operations) */
    return mbof_del_ancestors(delop);
}

static int mbof_del_ancestors(struct mbof_del_operation *delop)
{
    struct mbof_del_ancestors_ctx *anc_ctx;
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    struct ldb_context *ldb;
    struct mbof_dn_array *new_list;
    static const char *attrs[] = { DB_MEMBEROF, NULL };
    struct ldb_request *search;
    int ret;

    del_ctx = delop->del_ctx;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);
    anc_ctx = delop->anc_ctx;
    new_list = anc_ctx->new_list;

    ret = ldb_build_search_req(&search, ldb, anc_ctx,
                               new_list->dns[anc_ctx->cur],
                               LDB_SCOPE_BASE, NULL, attrs, NULL,
                               delop, mbof_del_anc_callback,
                               ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_request(ldb, search);
}

static int mbof_del_anc_callback(struct ldb_request *req,
                                 struct ldb_reply *ares)
{
    struct mbof_del_ancestors_ctx *anc_ctx;
    struct mbof_del_operation *delop;
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    struct ldb_context *ldb;
    struct ldb_message *msg;
    const struct ldb_message_element *el;
    struct mbof_dn_array *new_list;
    struct ldb_dn *valdn;
    int i, j, ret;

    delop = talloc_get_type(req->context, struct mbof_del_operation);
    del_ctx = delop->del_ctx;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);
    anc_ctx = delop->anc_ctx;
    new_list = anc_ctx->new_list;

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        msg = ares->message;

        if (anc_ctx->entry != NULL) {
            ldb_debug(ldb, LDB_DEBUG_TRACE,
                           "Found multiple entries for (%s)",
                           ldb_dn_get_linearized(anc_ctx->entry->dn));
            /* more than one entry per dn ?? db corrupted ? */
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        anc_ctx->entry = talloc_steal(anc_ctx, msg);
        if (anc_ctx->entry == NULL) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }
        break;
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        if (anc_ctx->entry == NULL) {
            /* no target, no party! */
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        /* check entry */
        el = ldb_msg_find_element(anc_ctx->entry, DB_MEMBEROF);
        if (el) {
            for (i = 0; i < el->num_values; i++) {
                valdn = ldb_dn_from_ldb_val(new_list, ldb, &el->values[i]);
                if (!valdn) {
                    ldb_debug(ldb, LDB_DEBUG_TRACE,
                                   "Invalid dn for memberof: (%s)",
                                   (const char *)el->values[i].data);
                    return ldb_module_done(ctx->req, NULL, NULL,
                                           LDB_ERR_OPERATIONS_ERROR);
                }
                for (j = 0; j < new_list->num; j++) {
                    if (ldb_dn_compare(valdn, new_list->dns[j]) == 0)
                        break;
                }
                if (j < new_list->num) {
                    talloc_free(valdn);
                    continue;
                }
                new_list->dns = talloc_realloc(new_list,
                                               new_list->dns,
                                               struct ldb_dn *,
                                               new_list->num + 1);
                if (!new_list->dns) {
                    return ldb_module_done(ctx->req, NULL, NULL,
                                           LDB_ERR_OPERATIONS_ERROR);
                }
                new_list->dns[new_list->num] = valdn;
                new_list->num++;
            }
        }

        /* done with this one */
        talloc_free(anc_ctx->entry);
        anc_ctx->entry = NULL;
        anc_ctx->cur++;

        /* check if we need to process any more */
        if (anc_ctx->cur < anc_ctx->num_direct) {
            /* ok process the next one */
            ret = mbof_del_ancestors(delop);
        } else {
            /* ok, end of the story, proceed to modify the entry */
            ret = mbof_del_mod_entry(delop);
        }

        if (ret != LDB_SUCCESS) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_del_mod_entry(struct mbof_del_operation *delop)
{
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    struct ldb_context *ldb;
    struct mbof_dn_array *new_list;
    struct ldb_request *mod_req;
    struct ldb_message *msg;
    struct ldb_message_element *el;
    struct ldb_dn **diff = NULL;
    const char *name;
    const char *val;
    int i, j, k;
    bool is_user;
    int ret;

    del_ctx = delop->del_ctx;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);
    new_list = delop->anc_ctx->new_list;

    /* if this is a user we need to find out which entries have been
     * removed so that we can later schedule removal of memberuid
     * attributes from these entries */
    ret = entry_is_user_object(delop->entry);
    switch (ret) {
    case LDB_SUCCESS:
        /* it's a user object  */
        is_user = true;
        break;
    case LDB_ERR_NO_SUCH_ATTRIBUTE:
        /* it is not a user object, continue */
        is_user = false;
        break;
    default:
        /* an error occured, return */
        return ret;
    }

    if (is_user) {
        /* prepare memberuid delete list */
        /* copy all original memberof entries, and then later remove
         * the ones that will survive in the entry */
        el = ldb_msg_find_element(delop->entry, DB_MEMBEROF);
        if (!el || !el->num_values) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
        diff = talloc_array(del_ctx->muops, struct ldb_dn *,
                            el->num_values + 1);
        if (!diff) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
        for (i = 0, j = 0; i < el->num_values; i++) {
            diff[j] = ldb_dn_from_ldb_val(diff, ldb, &el->values[i]);
            if (!diff[j]) {
                return LDB_ERR_OPERATIONS_ERROR;
            }
            /* skip the deleted entry if this is a delete op */
            if (!del_ctx->is_mod) {
                if (ldb_dn_compare(del_ctx->first->entry_dn, diff[j]) == 0) {
                    continue;
                }
            }
            j++;
        }
        /* zero terminate array */
        diff[j] = NULL;
    }

    /* change memberof on entry */
    msg = ldb_msg_new(delop);
    if (!msg) return LDB_ERR_OPERATIONS_ERROR;

    msg->dn = delop->entry_dn;

    if (new_list->num) {
        ret = ldb_msg_add_empty(msg, DB_MEMBEROF, LDB_FLAG_MOD_REPLACE, &el);
        if (ret != LDB_SUCCESS) {
            return ret;
        }

        el->values = talloc_array(el, struct ldb_val, new_list->num);
        if (!el->values) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
        for (i = 0, j = 0; i < new_list->num; i++) {
            if (ldb_dn_compare(new_list->dns[i], msg->dn) == 0)
                continue;
            val = ldb_dn_get_linearized(new_list->dns[i]);
            if (!val) {
                return LDB_ERR_OPERATIONS_ERROR;
            }
            el->values[j].length = strlen(val);
            el->values[j].data = (uint8_t *)talloc_strdup(el->values, val);
            if (!el->values[j].data) {
                return LDB_ERR_OPERATIONS_ERROR;
            }
            j++;

            if (is_user) {
                /* compare the entry's original memberof list with the new
                 * one and for each missing entry add a memberuid removal
                 * operation */
                for (k = 0; diff[k]; k++) {
                    if (ldb_dn_compare(new_list->dns[i], diff[k]) == 0) {
                        break;
                    }
                }
                if (diff[k]) {
                    talloc_zfree(diff[k]);
                    for (; diff[k + 1]; k++) {
                        diff[k] = diff[k + 1];
                    }
                    diff[k] = NULL;
                }
            }
        }
        el->num_values = j;

    }
    else {
        ret = ldb_msg_add_empty(msg, DB_MEMBEROF, LDB_FLAG_MOD_DELETE, &el);
        if (ret != LDB_SUCCESS) {
            return ret;
        }
    }

    if (is_user && diff[0]) {
        /* file memberuid removal operations */
        name = ldb_msg_find_attr_as_string(delop->entry, DB_NAME, NULL);
        if (!name) {
            return LDB_ERR_OPERATIONS_ERROR;
        }

        for (i = 0; diff[i]; i++) {
            ret = mbof_append_muop(del_ctx, &del_ctx->muops,
                                   &del_ctx->num_muops,
                                   LDB_FLAG_MOD_DELETE,
                                   diff[i], name);
            if (ret != LDB_SUCCESS) {
                return ret;
            }
        }
    }

    ret = ldb_build_mod_req(&mod_req, ldb, delop,
                            msg, NULL,
                            delop, mbof_del_mod_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }
    talloc_steal(mod_req, msg);

    return ldb_next_request(ctx->module, mod_req);
}

static int mbof_del_mod_callback(struct ldb_request *req,
                                 struct ldb_reply *ares)
{
    struct mbof_del_operation *delop;
    struct mbof_del_ctx *del_ctx;
    struct ldb_context *ldb;
    struct mbof_ctx *ctx;
    int ret;

    delop = talloc_get_type(req->context, struct mbof_del_operation);
    del_ctx = delop->del_ctx;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        ldb_debug(ldb, LDB_DEBUG_TRACE, "Got an entry on a non search op ?!");
        /* shouldn't happen */
        talloc_zfree(ares);
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    case LDB_REPLY_REFERRAL:
        /* ignore */
        talloc_zfree(ares);
        break;

    case LDB_REPLY_DONE:

        ret = mbof_del_progeny(delop);

        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }
    }

    return LDB_SUCCESS;
}

static int mbof_mod_add(struct mbof_mod_ctx *mod_ctx,
                        struct mbof_dn_array *ael);

static int mbof_del_progeny(struct mbof_del_operation *delop)
{
    struct mbof_ctx *ctx;
    struct mbof_del_ctx *del_ctx;
    struct mbof_del_operation *nextop;
    const struct ldb_message_element *el;
    struct ldb_context *ldb;
    struct ldb_dn *valdn;
    int i, ret;

    del_ctx = delop->del_ctx;
    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    /* now verify if this entry is a group and members need to be processed as
     * well */

    el = ldb_msg_find_element(delop->entry, DB_MEMBER);
    if (el) {
        for (i = 0; i < el->num_values; i++) {
            valdn = ldb_dn_from_ldb_val(delop, ldb, &el->values[i]);
            if (!valdn || !ldb_dn_validate(valdn)) {
                ldb_debug(ldb, LDB_DEBUG_TRACE,
                               "Invalid DN for member: (%s)",
                               (const char *)el->values[i].data);
                return LDB_ERR_INVALID_DN_SYNTAX;
            }
            ret = mbof_append_delop(delop, valdn);
            if (ret != LDB_SUCCESS) {
                return ret;
            }
        }
    }

    /* finally find the next entry to handle */
    ret = mbof_del_get_next(delop, &nextop);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    if (nextop) {
        return mbof_del_execute_op(nextop);
    }

    /* see if there are memberuid operations to perform */
    if (del_ctx->muops) {
        return mbof_del_muop(del_ctx);
    }
    /* see if there are follow functions to run */
    if (del_ctx->follow_mod) {
        return mbof_mod_add(del_ctx->follow_mod,
                            del_ctx->follow_mod->to_add);
    }

    /* ok, no more ops, this means our job is done */
    return ldb_module_done(ctx->req,
                           ctx->ret_ctrls,
                           ctx->ret_resp,
                           LDB_SUCCESS);
}

static int mbof_del_get_next(struct mbof_del_operation *delop,
                             struct mbof_del_operation **nextop)
{
    struct mbof_del_operation *top, *cop;
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    struct mbof_dn *save, *tmp;

    del_ctx = delop->del_ctx;
    ctx = del_ctx->ctx;

    /* first of all, save the current delop in the history */
    save = talloc_zero(del_ctx, struct mbof_dn);
    if (!save) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    save->dn = delop->entry_dn;

    if (del_ctx->history) {
        tmp = del_ctx->history;
        while (tmp->next) tmp = tmp->next;
        tmp->next = save;
    } else {
        del_ctx->history = save;
    }

    /* Find next one */
    for (top = delop; top; top = top->parent) {
        if (top->num_children == 0 || top->next_child >= top->num_children) {
            /* no children, go for next one */
            continue;
        }

        while (top->next_child < top->num_children) {
            cop = top->children[top->next_child];
            top->next_child++;

            /* verify this operation has not already been performed */
            for (tmp = del_ctx->history; tmp; tmp = tmp->next) {
                if (ldb_dn_compare(tmp->dn, cop->entry_dn) == 0) {
                    break;
                }
            }
            if (tmp == NULL) {
                /* and return the current one */
                *nextop = cop;
                return LDB_SUCCESS;
            }
        }
    }

    /* we have no more ops */
    *nextop = NULL;
    return LDB_SUCCESS;
}

static int mbof_del_fill_muop(struct mbof_del_ctx *del_ctx,
                              struct ldb_message *entry)
{
    struct ldb_message_element *el;
    char *name;
    int ret;
    int i;

    el = ldb_msg_find_element(entry, DB_MEMBEROF);
    if (!el || el->num_values == 0) {
        /* no memberof attributes ... */
        return LDB_SUCCESS;
    }

    ret = entry_is_user_object(entry);
    switch (ret) {
    case LDB_SUCCESS:
        /* it's a user object, continue */
        break;

    case LDB_ERR_NO_SUCH_ATTRIBUTE:
        /* it is not a user object, just return */
        return LDB_SUCCESS;

    default:
        /* an error occured, return */
        return ret;
    }

    name = talloc_strdup(del_ctx,
                         ldb_msg_find_attr_as_string(entry, DB_NAME, NULL));
    if (!name) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    for (i = 0; i < el->num_values; i++) {
        struct ldb_dn *valdn;

        valdn = ldb_dn_from_ldb_val(del_ctx->muops,
                                    ldb_module_get_ctx(del_ctx->ctx->module),
                                    &el->values[i]);
        if (!valdn || !ldb_dn_validate(valdn)) {
            ldb_debug(ldb_module_get_ctx(del_ctx->ctx->module),
                      LDB_DEBUG_ERROR,
                      "Invalid dn value: [%s]",
                      (const char *)el->values[i].data);
        }

        ret = mbof_append_muop(del_ctx, &del_ctx->muops,
                               &del_ctx->num_muops,
                               LDB_FLAG_MOD_DELETE,
                               valdn, name);
        if (ret != LDB_SUCCESS) {
            return ret;
        }
    }

    return LDB_SUCCESS;
}

/* del memberuid attributes to parent groups */
static int mbof_del_muop(struct mbof_del_ctx *del_ctx)
{
    struct ldb_context *ldb;
    struct ldb_message *msg;
    struct ldb_request *mod_req;
    struct mbof_ctx *ctx;
    int ret;

    ctx = del_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    msg = ldb_msg_new(del_ctx);
    if (!msg) return LDB_ERR_OPERATIONS_ERROR;

    msg->dn = del_ctx->muops[del_ctx->cur_muop].dn;
    msg->elements = del_ctx->muops[del_ctx->cur_muop].el;
    msg->num_elements = 1;

    ret = ldb_build_mod_req(&mod_req, ldb, del_ctx,
                            msg, NULL,
                            del_ctx, mbof_del_muop_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_next_request(ctx->module, mod_req);
}

static int mbof_del_muop_callback(struct ldb_request *req,
                                  struct ldb_reply *ares)
{
    struct mbof_del_ctx *del_ctx;
    struct mbof_ctx *ctx;
    int ret;

    del_ctx = talloc_get_type(req->context, struct mbof_del_ctx);
    ctx = del_ctx->ctx;

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        /* shouldn't happen */
        talloc_zfree(ares);
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        del_ctx->cur_muop++;
        if (del_ctx->cur_muop < del_ctx->num_muops) {
            ret = mbof_del_muop(del_ctx);
        }
        /* see if there are follow functions to run */
        else if (del_ctx->follow_mod) {
            return mbof_mod_add(del_ctx->follow_mod,
                                del_ctx->follow_mod->to_add);
        }
        else {
            return ldb_module_done(ctx->req,
                                   ctx->ret_ctrls,
                                   ctx->ret_resp,
                                   LDB_SUCCESS);
        }

        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}



/* mod operation */

/* A modify operation just implements either an add operation, or a delete
 * operation or both (replace) in turn.
 * The only difference between a modify and a pure add or a pure delete is that
 * the object is not created a new or not completely removed, but the setup just
 * treats it in the same way children objects are treated in a pure add or delete
 * operation. A list of appropriate parents and objects to modify is built, then
 * we jump directly in the add or delete code.
 * If both add and delete are necessary, delete operations are performed first
 * and then a followup add operation is concatenated */

static int mbof_mod_callback(struct ldb_request *req,
                             struct ldb_reply *ares);
static int mbof_orig_mod(struct mbof_mod_ctx *mod_ctx);
static int mbof_orig_mod_callback(struct ldb_request *req,
                                  struct ldb_reply *ares);
static int mbof_mod_process(struct mbof_mod_ctx *mod_ctx, bool *done);
static int mbof_mod_delete(struct mbof_mod_ctx *mod_ctx,
                           struct mbof_dn_array *del);
static int mbof_fill_dn_array(TALLOC_CTX *memctx,
                              struct ldb_context *ldb,
                              const struct ldb_message_element *el,
                              struct mbof_dn_array **dn_array);

static int memberof_mod(struct ldb_module *module, struct ldb_request *req)
{
    struct ldb_message_element *el;
    struct mbof_mod_ctx *mod_ctx;
    struct mbof_ctx *ctx;
    static const char *attrs[] = {DB_MEMBER, DB_MEMBEROF, NULL};
    struct ldb_context *ldb = ldb_module_get_ctx(module);
    struct ldb_request *search;
    int ret;

    if (ldb_dn_is_special(req->op.mod.message->dn)) {
        /* do not manipulate our control entries */
        return ldb_next_request(module, req);
    }

    /* check if memberof is specified */
    el = ldb_msg_find_element(req->op.mod.message, DB_MEMBEROF);
    if (el) {
        ldb_debug(ldb, LDB_DEBUG_ERROR,
                  "Error: the memberof attribute is readonly.");
        return LDB_ERR_UNWILLING_TO_PERFORM;
    }

    /* check if memberuid is specified */
    el = ldb_msg_find_element(req->op.mod.message, DB_MEMBERUID);
    if (el) {
        ldb_debug(ldb, LDB_DEBUG_ERROR,
                  "Error: the memberuid attribute is readonly.");
        return LDB_ERR_UNWILLING_TO_PERFORM;
    }

    ctx = mbof_init(module, req);
    if (!ctx) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    mod_ctx = talloc_zero(ctx, struct mbof_mod_ctx);
    if (!mod_ctx) {
        talloc_free(ctx);
        return LDB_ERR_OPERATIONS_ERROR;
    }
    mod_ctx->ctx = ctx;

    mod_ctx->msg = ldb_msg_copy(mod_ctx, req->op.mod.message);
    if (!mod_ctx->msg) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    /* continue with normal ops if there are no members */
    el = ldb_msg_find_element(mod_ctx->msg, DB_MEMBER);
    if (!el) {
        mod_ctx->terminate = true;
        return mbof_orig_mod(mod_ctx);
    }

    mod_ctx->membel = el;

    /* can't do anything,
     * must check first what's on the entry */
    ret = ldb_build_search_req(&search, ldb, mod_ctx,
                               mod_ctx->msg->dn, LDB_SCOPE_BASE,
                               NULL, attrs, NULL,
                               mod_ctx, mbof_mod_callback,
                               req);
    if (ret != LDB_SUCCESS) {
        talloc_free(ctx);
        return ret;
    }

    return ldb_request(ldb, search);
}


static int mbof_mod_callback(struct ldb_request *req,
                             struct ldb_reply *ares)
{
    struct mbof_mod_ctx *mod_ctx;
    struct ldb_context *ldb;
    struct mbof_ctx *ctx;
    int ret;

    mod_ctx = talloc_get_type(req->context, struct mbof_mod_ctx);
    ctx = mod_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        if (mod_ctx->entry != NULL) {
            ldb_debug(ldb, LDB_DEBUG_TRACE,
                           "Found multiple entries for (%s)",
                           ldb_dn_get_linearized(mod_ctx->msg->dn));
            /* more than one entry per dn ?? db corrupted ? */
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        mod_ctx->entry = talloc_steal(mod_ctx, ares->message);
        if (mod_ctx->entry == NULL) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }
        break;
    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        if (mod_ctx->entry == NULL) {
            ldb_debug(ldb, LDB_DEBUG_TRACE, "Entry not found (%s)",
                           ldb_dn_get_linearized(mod_ctx->msg->dn));
            /* this target does not exists, too bad! */
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_NO_SUCH_OBJECT);
        }

        ret = mbof_orig_mod(mod_ctx);
        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_orig_mod(struct mbof_mod_ctx *mod_ctx)
{
    struct ldb_request *mod_req;
    struct ldb_context *ldb;
    struct mbof_ctx *ctx;
    int ret;

    ctx = mod_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    ret = ldb_build_mod_req(&mod_req, ldb, ctx->req,
                            mod_ctx->msg, ctx->req->controls,
                            mod_ctx, mbof_orig_mod_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_next_request(ctx->module, mod_req);
}

static int mbof_orig_mod_callback(struct ldb_request *req,
                                  struct ldb_reply *ares)
{
    struct ldb_context *ldb;
    struct mbof_mod_ctx *mod_ctx;
    struct mbof_ctx *ctx;
    int ret;

    mod_ctx = talloc_get_type(req->context, struct mbof_mod_ctx);
    ctx = mod_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    if (ares->type != LDB_REPLY_DONE) {
        talloc_zfree(ares);
        ldb_debug(ldb, LDB_DEBUG_TRACE, "Invalid reply type!");
        ldb_set_errstring(ldb, "Invalid reply type!");
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }

    /* save real call stuff */
    ctx->ret_ctrls = talloc_steal(ctx, ares->controls);
    ctx->ret_resp = talloc_steal(ctx, ares->response);

    if (!mod_ctx->terminate) {
        /* next step */
        ret = mbof_mod_process(mod_ctx, &mod_ctx->terminate);
        if (ret != LDB_SUCCESS) {
            talloc_zfree(ares);
            return ldb_module_done(ctx->req, NULL, NULL, ret);
        }
    }

    if (mod_ctx->terminate) {
        talloc_zfree(ares);
        return ldb_module_done(ctx->req,
                               ctx->ret_ctrls,
                               ctx->ret_resp,
                               LDB_SUCCESS);
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_mod_process(struct mbof_mod_ctx *mod_ctx, bool *done)
{
    const struct ldb_message_element *el;
    struct ldb_context *ldb;
    struct mbof_ctx *ctx;
    struct mbof_dn_array *removed;
    struct mbof_dn_array *added;
    int i, j, ret;

    ctx = mod_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    switch (mod_ctx->membel->flags) {
    case LDB_FLAG_MOD_ADD:

        ret = mbof_fill_dn_array(mod_ctx, ldb, mod_ctx->membel, &added);
        if (ret != LDB_SUCCESS) {
            return ret;
        }

        return mbof_mod_add(mod_ctx, added);

    case LDB_FLAG_MOD_DELETE:

        if (mod_ctx->membel->num_values == 0) {
            el = ldb_msg_find_element(mod_ctx->entry, DB_MEMBER);
        } else {
            el = mod_ctx->membel;
        }

        if (!el) {
            /* nothing to do really */
            *done = true;
            return LDB_SUCCESS;
        }

        ret = mbof_fill_dn_array(mod_ctx, ldb, el, &removed);
        if (ret != LDB_SUCCESS) {
            return ret;
        }

        return mbof_mod_delete(mod_ctx, removed);

    case LDB_FLAG_MOD_REPLACE:

        removed = NULL;
        el = ldb_msg_find_element(mod_ctx->entry, DB_MEMBER);
        if (el) {
            ret = mbof_fill_dn_array(mod_ctx, ldb, el, &removed);
            if (ret != LDB_SUCCESS) {
                return ret;
            }
        }

        added = NULL;
        el = mod_ctx->membel;
        if (el) {
            ret = mbof_fill_dn_array(mod_ctx, ldb, el, &added);
            if (ret != LDB_SUCCESS) {
                return ret;
            }
        }

        /* remove from arrays values that ended up unchanged */
        if (removed && removed->num && added && added->num) {
            for (i = 0; i < added->num; i++) {
                for (j = 0; j < removed->num; j++) {
                    if (ldb_dn_compare(added->dns[i], removed->dns[j]) == 0) {
                        break;
                    }
                }
                if (j < removed->num) {
                    /* preexisting one, not removed, nor added */
                    for (; j+1 < removed->num; j++) {
                        removed->dns[j] = removed->dns[j+1];
                    }
                    removed->num--;
                    for (j = i; j+1 < added->num; j++) {
                        added->dns[j] = added->dns[j+1];
                    }
                    added->num--;
                }
            }
        }

        /* if we need to add something put it away so that it
         * can be done after all delete operations are over */
        if (added && added->num) {
            mod_ctx->to_add = added;
        }

        /* if we have something to remove do it first */
        if (removed && removed->num) {
            return mbof_mod_delete(mod_ctx, removed);
        }

        /* if there is nothing to remove and we have stuff to add
         * do it right away */
        if (mod_ctx->to_add) {
            return mbof_mod_add(mod_ctx, added);
        }

        /* the replacement function resulted in a null op,
         * nothing to do, return happily */
        *done = true;
        return LDB_SUCCESS;
    }

    return LDB_ERR_OPERATIONS_ERROR;
}

static int mbof_mod_add(struct mbof_mod_ctx *mod_ctx,
                        struct mbof_dn_array *ael)
{
    const struct ldb_message_element *el;
    struct mbof_dn_array *parents;
    struct mbof_add_ctx *add_ctx;
    struct ldb_context *ldb;
    struct mbof_ctx *ctx;
    int i, ret;

    ctx = mod_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    el = ldb_msg_find_element(mod_ctx->entry, DB_MEMBEROF);

    /* all the parents + itself */
    ret = mbof_fill_dn_array(mod_ctx, ldb, el, &parents);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    parents->dns = talloc_realloc(parents, parents->dns,
                                  struct ldb_dn *, parents->num + 1);
    if (!parents->dns) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    parents->dns[parents->num] = mod_ctx->entry->dn;
    parents->num++;

    add_ctx = talloc_zero(mod_ctx, struct mbof_add_ctx);
    if (!add_ctx) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    add_ctx->ctx = ctx;
    add_ctx->msg_dn = mod_ctx->msg->dn;

    for (i = 0; i < ael->num; i++) {
        ret = mbof_append_addop(add_ctx, parents, ael->dns[i]);
        if (ret != LDB_SUCCESS) {
            return ret;
        }
    }

    return mbof_next_add(add_ctx->add_list);
}

static int mbof_mod_delete(struct mbof_mod_ctx *mod_ctx,
                           struct mbof_dn_array *del)
{
    struct mbof_del_operation *first;
    struct mbof_del_ctx *del_ctx;
    struct ldb_context *ldb;
    struct mbof_ctx *ctx;
    int i, ret;

    ctx = mod_ctx->ctx;
    ldb = ldb_module_get_ctx(ctx->module);

    del_ctx = talloc_zero(mod_ctx, struct mbof_del_ctx);
    if (!del_ctx) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    del_ctx->ctx = ctx;
    del_ctx->is_mod = true;

    /* create first entry */
    /* the first entry is the parent of all entries and the one where we
     * remove member from, it does not get the same treatment as others */
    first = talloc_zero(del_ctx, struct mbof_del_operation);
    if (!first) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    del_ctx->first = first;

    first->del_ctx = del_ctx;
    first->entry = mod_ctx->entry;
    first->entry_dn = mod_ctx->entry->dn;

    /* prepare del sets */
    for (i = 0; i < del->num; i++) {
        ret = mbof_append_delop(first, del->dns[i]);
        if (ret != LDB_SUCCESS) {
            return ret;
        }
    }

    /* add followup function if we also have stuff to add */
    if (mod_ctx->to_add) {
        del_ctx->follow_mod = mod_ctx;
    }

    /* now that sets are built, start processing */
    return mbof_del_execute_op(first->children[0]);
}

static int mbof_fill_dn_array(TALLOC_CTX *memctx,
                              struct ldb_context *ldb,
                              const struct ldb_message_element *el,
                              struct mbof_dn_array **dn_array)
{
    struct mbof_dn_array *ar;
    struct ldb_dn *valdn;
    int i;

    ar = talloc_zero(memctx, struct mbof_dn_array);
    if (!ar) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    *dn_array = ar;

    if (!el || el->num_values == 0) {
        return LDB_SUCCESS;
    }

    ar->dns = talloc_array(ar, struct ldb_dn *, el->num_values);
    if (!ar->dns) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    ar->num = el->num_values;

    for (i = 0; i < ar->num; i++) {
        valdn = ldb_dn_from_ldb_val(ar, ldb, &el->values[i]);
        if (!valdn || !ldb_dn_validate(valdn)) {
            ldb_debug(ldb, LDB_DEBUG_TRACE, "Invalid dn value: [%s]",
                                            (const char *)el->values[i].data);
            return LDB_ERR_INVALID_DN_SYNTAX;
        }
        ar->dns[i] = valdn;
    }

    return LDB_SUCCESS;
}


/*************************
 * Cleanup task routines *
 *************************/

struct mbof_member {
    struct mbof_member *prev;
    struct mbof_member *next;

    struct ldb_dn *dn;
    const char *name;
    bool orig_has_memberof;
    bool orig_has_memberuid;
    struct ldb_message_element *orig_members;

    struct mbof_member **members;

    hash_table_t *memberofs;

    struct ldb_message_element *memuids;

    enum { MBOF_GROUP_TO_DO = 0,
           MBOF_GROUP_DONE,
           MBOF_USER,
           MBOF_ITER_ERROR } status;
};

struct mbof_rcmp_context {
    struct ldb_module *module;
    struct ldb_request *req;

    struct mbof_member *user_list;
    hash_table_t *user_table;

    struct mbof_member *group_list;
    hash_table_t *group_table;
};

static void *hash_alloc(const size_t size, void *pvt)
{
    return talloc_size(pvt, size);
}

static void hash_free(void *ptr, void *pvt)
{
    talloc_free(ptr);
}

static int mbof_steal_msg_el(TALLOC_CTX *memctx,
                             const char *name,
                             struct ldb_message *msg,
                             struct ldb_message_element **_dest)
{
    struct ldb_message_element *src;
    struct ldb_message_element *dest;

    src = ldb_msg_find_element(msg, name);
    if (!src) {
        return LDB_ERR_NO_SUCH_ATTRIBUTE;
    }

    dest = talloc_zero(memctx, struct ldb_message_element);
    if (!dest) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    *dest = *src;
    talloc_steal(dest, dest->name);
    talloc_steal(dest, dest->values);

    *_dest = dest;
    return LDB_SUCCESS;
}

static int mbof_rcmp_usr_callback(struct ldb_request *req,
                                  struct ldb_reply *ares);
static int mbof_rcmp_search_groups(struct mbof_rcmp_context *ctx);
static int mbof_rcmp_grp_callback(struct ldb_request *req,
                                  struct ldb_reply *ares);
static int mbof_member_update(struct mbof_rcmp_context *ctx,
                              struct mbof_member *parent,
                              struct mbof_member *mem);
static bool mbof_member_iter(hash_entry_t *item, void *user_data);
static int mbof_add_memuid(struct mbof_member *grp, const char *user);
static int mbof_rcmp_update(struct mbof_rcmp_context *ctx);
static int mbof_rcmp_mod_callback(struct ldb_request *req,
                                  struct ldb_reply *ares);

static int memberof_recompute_task(struct ldb_module *module,
                                   struct ldb_request *req)
{
    struct ldb_context *ldb = ldb_module_get_ctx(module);
    static const char *attrs[] = { DB_NAME, DB_MEMBEROF, NULL };
    static const char *filter = "(objectclass=user)";
    struct mbof_rcmp_context *ctx;
    struct ldb_request *src_req;
    int ret;

    ctx = talloc_zero(req, struct mbof_rcmp_context);
    if (!ctx) {
        return LDB_ERR_OPERATIONS_ERROR;
    }
    ctx->module = module;
    ctx->req = req;

    ret = hash_create_ex(1024, &ctx->user_table, 0, 0, 0, 0,
                         hash_alloc, hash_free, ctx, NULL, NULL);
    if (ret != HASH_SUCCESS) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    ret = ldb_build_search_req(&src_req, ldb, ctx,
                               NULL, LDB_SCOPE_SUBTREE,
                               filter, attrs, NULL,
                               ctx, mbof_rcmp_usr_callback, ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_request(ldb, src_req);
}

static int mbof_rcmp_usr_callback(struct ldb_request *req,
                                  struct ldb_reply *ares)
{
    struct mbof_rcmp_context *ctx;
    struct mbof_member *usr;
    hash_value_t value;
    hash_key_t key;
    const char *name;
    int ret;

    ctx = talloc_get_type(req->context, struct mbof_rcmp_context);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:

        usr = talloc_zero(ctx, struct mbof_member);
        if (!usr) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        usr->status = MBOF_USER;
        usr->dn = talloc_steal(usr, ares->message->dn);
        name = ldb_msg_find_attr_as_string(ares->message, DB_NAME, NULL);
        if (name) {
            usr->name = talloc_steal(usr, name);
        }

        if (ldb_msg_find_element(ares->message, DB_MEMBEROF)) {
            usr->orig_has_memberof = true;
        }

        DLIST_ADD(ctx->user_list, usr);

        key.type = HASH_KEY_STRING;
        key.str = discard_const(ldb_dn_get_linearized(usr->dn));
        value.type = HASH_VALUE_PTR;
        value.ptr = usr;

        ret = hash_enter(ctx->user_table, &key, &value);
        if (ret != HASH_SUCCESS) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        break;

    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        talloc_zfree(ares);

        /* and now search groups */
        return mbof_rcmp_search_groups(ctx);
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_rcmp_search_groups(struct mbof_rcmp_context *ctx)
{
    struct ldb_context *ldb = ldb_module_get_ctx(ctx->module);
    static const char *attrs[] = { DB_MEMBEROF, DB_MEMBERUID,
                                   DB_NAME, DB_MEMBER, NULL };
    static const char *filter = "(objectclass=group)";
    struct ldb_request *req;
    int ret;

    ret = hash_create_ex(1024, &ctx->group_table, 0, 0, 0, 0,
                         hash_alloc, hash_free, ctx, NULL, NULL);
    if (ret != HASH_SUCCESS) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }

    ret = ldb_build_search_req(&req, ldb, ctx,
                               NULL, LDB_SCOPE_SUBTREE,
                               filter, attrs, NULL,
                               ctx, mbof_rcmp_grp_callback, ctx->req);
    if (ret != LDB_SUCCESS) {
        return ret;
    }

    return ldb_request(ldb, req);
}

static int mbof_rcmp_grp_callback(struct ldb_request *req,
                                  struct ldb_reply *ares)
{
    struct ldb_context *ldb;
    struct mbof_rcmp_context *ctx;
    struct ldb_message_element *el;
    struct mbof_member *iter;
    struct mbof_member *grp;
    hash_value_t value;
    hash_key_t key;
    const char *name;
    int i, j;
    int ret;

    ctx = talloc_get_type(req->context, struct mbof_rcmp_context);
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:

        grp = talloc_zero(ctx, struct mbof_member);
        if (!grp) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        grp->status = MBOF_GROUP_TO_DO;
        grp->dn = talloc_steal(grp, ares->message->dn);
        grp->name = ldb_msg_find_attr_as_string(ares->message, DB_NAME, NULL);
        name = ldb_msg_find_attr_as_string(ares->message, DB_NAME, NULL);
        if (name) {
            grp->name = talloc_steal(grp, name);
        }

        if (ldb_msg_find_element(ares->message, DB_MEMBEROF)) {
            grp->orig_has_memberof = true;
        }

        if (ldb_msg_find_element(ares->message, DB_MEMBERUID)) {
            grp->orig_has_memberuid = true;
        }

        ret = mbof_steal_msg_el(grp, DB_MEMBER,
                                ares->message, &grp->orig_members);
        if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_ATTRIBUTE) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        DLIST_ADD(ctx->group_list, grp);

        key.type = HASH_KEY_STRING;
        key.str = discard_const(ldb_dn_get_linearized(grp->dn));
        value.type = HASH_VALUE_PTR;
        value.ptr = grp;

        ret = hash_enter(ctx->group_table, &key, &value);
        if (ret != HASH_SUCCESS) {
            return ldb_module_done(ctx->req, NULL, NULL,
                                   LDB_ERR_OPERATIONS_ERROR);
        }

        break;

    case LDB_REPLY_REFERRAL:
        /* ignore */
        break;

    case LDB_REPLY_DONE:
        talloc_zfree(ares);

        if (!ctx->group_list) {
            /* no groups ? */
            return ldb_module_done(ctx->req, NULL, NULL, LDB_SUCCESS);
        }

        /* for each group compute the members list */
        for (iter = ctx->group_list; iter; iter = iter->next) {

            el = iter->orig_members;
            if (!el || el->num_values == 0) {
                /* no members */
                continue;
            }

            /* we have at most num_values group members */
            iter->members = talloc_array(iter, struct mbof_member *,
                                         el->num_values +1);
            if (!iter->members) {
                return ldb_module_done(ctx->req, NULL, NULL,
                                       LDB_ERR_OPERATIONS_ERROR);
            }

            for (i = 0, j = 0; i < el->num_values; i++) {
                key.type = HASH_KEY_STRING;
                key.str = (char *)el->values[i].data;

                ret = hash_lookup(ctx->user_table, &key, &value);
                switch (ret) {
                case HASH_SUCCESS:
                    iter->members[j] = (struct mbof_member *)value.ptr;
                    j++;
                    break;

                case HASH_ERROR_KEY_NOT_FOUND:
                    /* not a user, see if it is a group */

                    ret = hash_lookup(ctx->group_table, &key, &value);
                    if (ret != HASH_SUCCESS) {
                        if (ret != HASH_ERROR_KEY_NOT_FOUND) {
                            return ldb_module_done(ctx->req, NULL, NULL,
                                                   LDB_ERR_OPERATIONS_ERROR);
                        }
                    }
                    if (ret == HASH_ERROR_KEY_NOT_FOUND) {
                        /* not a known user, nor a known group ?
                           give a warning an continue */
                        ldb_debug(ldb, LDB_DEBUG_ERROR,
                                  "member attribute [%s] has no corresponding"
                                  " entry!", key.str);
                        break;
                    }

                    iter->members[j] = (struct mbof_member *)value.ptr;
                    j++;
                    break;

                default:
                    return ldb_module_done(ctx->req, NULL, NULL,
                                           LDB_ERR_OPERATIONS_ERROR);
                }
            }
            /* terminate */
            iter->members[j] = NULL;

            talloc_zfree(iter->orig_members);
        }

        /* now generate correct memberof tables */
        while (ctx->group_list->status == MBOF_GROUP_TO_DO) {

            grp = ctx->group_list;

            /* move to end of list and mark as done.
             * NOTE: this is not efficient, but will do for now */
            DLIST_DEMOTE(ctx->group_list, grp, struct mbof_member *);
            grp->status = MBOF_GROUP_DONE;

            /* verify if members need updating */
            if (!grp->members) {
                continue;
            }
            for (i = 0; grp->members[i]; i++) {
                ret = mbof_member_update(ctx, grp, grp->members[i]);
                if (ret != LDB_SUCCESS) {
                    return ldb_module_done(ctx->req, NULL, NULL,
                                           LDB_ERR_OPERATIONS_ERROR);
                }
            }
        }

        /* ok all done, now go on and modify the tree */
        return mbof_rcmp_update(ctx);
    }

    talloc_zfree(ares);
    return LDB_SUCCESS;
}

static int mbof_member_update(struct mbof_rcmp_context *ctx,
                              struct mbof_member *parent,
                              struct mbof_member *mem)
{
    hash_value_t value;
    hash_key_t key;
    int ret;

    /* ignore loops */
    if (parent == mem) return LDB_SUCCESS;

    key.type = HASH_KEY_STRING;
    key.str = discard_const(ldb_dn_get_linearized(parent->dn));

    if (!mem->memberofs) {
        ret = hash_create_ex(32, &mem->memberofs, 0, 0, 0, 0,
                             hash_alloc, hash_free, mem, NULL, NULL);
        if (ret != HASH_SUCCESS) {
            return LDB_ERR_OPERATIONS_ERROR;
        }

        ret = HASH_ERROR_KEY_NOT_FOUND;

    } else {

        ret = hash_lookup(mem->memberofs, &key, &value);
        if (ret != HASH_SUCCESS) {
            if (ret != HASH_ERROR_KEY_NOT_FOUND) {
                /* fatal error */
                return LDB_ERR_OPERATIONS_ERROR;
            }
        }
    }

    if (ret == HASH_ERROR_KEY_NOT_FOUND) {

        /* it's missing, update member */
        value.type = HASH_VALUE_PTR;
        value.ptr = parent;

        ret = hash_enter(mem->memberofs, &key, &value);
        if (ret != HASH_SUCCESS) {
            return LDB_ERR_OPERATIONS_ERROR;
        }

        if (mem->status == MBOF_USER) {
            /* add corresponding memuid to the group */
            ret = mbof_add_memuid(parent, mem->name);
            if (ret != LDB_SUCCESS) {
                return ret;
            }
        }

        /* if we updated a group, mark it as TO DO again */
        if (mem->status == MBOF_GROUP_DONE) {
            mem->status = MBOF_GROUP_TO_DO;
        }
    }

    /* now see if the parent has memberofs to pass down */
    if (parent->memberofs) {
        ret = hash_iterate(parent->memberofs, mbof_member_iter, mem);
        if (ret != HASH_SUCCESS) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
        if (mem->status == MBOF_ITER_ERROR) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
    }

    /* finally, if it was made TO DO move it to the head */
    if (mem->status == MBOF_GROUP_TO_DO) {
        DLIST_PROMOTE(ctx->group_list, mem);
    }

    return LDB_SUCCESS;
}

static bool mbof_member_iter(hash_entry_t *item, void *user_data)
{
    struct mbof_member *parent;
    struct mbof_member *mem;
    hash_value_t value;
    int ret;

    mem = talloc_get_type(user_data, struct mbof_member);

    /* exclude self */
    if (strcmp(item->key.str, ldb_dn_get_linearized(mem->dn)) == 0) {
        return true;
    }

    /* check if we already have it */
    ret = hash_lookup(mem->memberofs, &item->key, &value);
    if (ret != HASH_SUCCESS) {
        if (ret != HASH_ERROR_KEY_NOT_FOUND) {
            /* fatal error */
            mem->status = MBOF_ITER_ERROR;
            return false;
        }

        /* was not already here, add it and mark group as TO DO */
        ret = hash_enter(mem->memberofs, &item->key, &item->value);
        if (ret != HASH_SUCCESS) {
            return LDB_ERR_OPERATIONS_ERROR;
        }

        if (mem->status == MBOF_GROUP_DONE) {
            mem->status = MBOF_GROUP_TO_DO;
        }

        if (mem->status == MBOF_USER) {
            /* add corresponding memuid to the group */
            parent = (struct mbof_member *)item->value.ptr;
            ret = mbof_add_memuid(parent, mem->name);
            if (ret != LDB_SUCCESS) {
                mem->status = MBOF_ITER_ERROR;
                return false;
            }
        }
    }

    return true;
}

static int mbof_add_memuid(struct mbof_member *grp, const char *user)
{
    struct ldb_val *vals;
    int n;

    if (!grp->memuids) {
        grp->memuids = talloc_zero(grp, struct ldb_message_element);
        if (!grp->memuids) {
            return LDB_ERR_OPERATIONS_ERROR;
        }

        grp->memuids->name = talloc_strdup(grp->memuids, DB_MEMBERUID);
        if (!grp->memuids->name) {
            return LDB_ERR_OPERATIONS_ERROR;
        }
    }

    n = grp->memuids->num_values;
    vals = talloc_realloc(grp->memuids,
                          grp->memuids->values,
                          struct ldb_val, n + 1);
    if (!vals) {
        return LDB_ERR_OPERATIONS_ERROR;
    }

    vals[n].data = (uint8_t *)talloc_strdup(vals, user);
    vals[n].length = strlen(user);

    grp->memuids->values = vals;
    grp->memuids->num_values = n + 1;

    return LDB_SUCCESS;
}

static int mbof_rcmp_update(struct mbof_rcmp_context *ctx)
{
    struct ldb_context *ldb = ldb_module_get_ctx(ctx->module);
    struct ldb_message_element *el;
    struct ldb_message *msg = NULL;
    struct ldb_request *req;
    struct mbof_member *x = NULL;
    hash_key_t *keys;
    unsigned long count;
    int flags;
    int ret, i;

    /* we process all users first and then all groups */
    if (ctx->user_list) {
        /* take the next entry and remove it from the list */
        x = ctx->user_list;
        DLIST_REMOVE(ctx->user_list, x);
    }
    else if (ctx->group_list) {
        /* take the next entry and remove it from the list */
        x = ctx->group_list;
        DLIST_REMOVE(ctx->group_list, x);
    }
    else {
        /* processing terminated, return */
        ret = LDB_SUCCESS;
        goto done;
    }

    msg = ldb_msg_new(ctx);
    if (!msg) {
        ret = LDB_ERR_OPERATIONS_ERROR;
        goto done;
    }

    msg->dn = x->dn;

    /* process memberof */
    if (x->memberofs) {
        ret = hash_keys(x->memberofs, &count, &keys);
        if (ret != HASH_SUCCESS) {
            ret = LDB_ERR_OPERATIONS_ERROR;
            goto done;
        }

        if (x->orig_has_memberof) {
            flags = LDB_FLAG_MOD_REPLACE;
        } else {
            flags = LDB_FLAG_MOD_ADD;
        }

        ret = ldb_msg_add_empty(msg, DB_MEMBEROF, flags, &el);
        if (ret != LDB_SUCCESS) {
            goto done;
        }

        el->values = talloc_array(el, struct ldb_val, count);
        if (!el->values) {
            ret = LDB_ERR_OPERATIONS_ERROR;
            goto done;
        }
        el->num_values = count;

        for (i = 0; i < count; i++) {
            el->values[i].data = (uint8_t *)keys[i].str;
            el->values[i].length = strlen(keys[i].str);
        }
    } else if (x->orig_has_memberof) {
        ret = ldb_msg_add_empty(msg, DB_MEMBEROF, LDB_FLAG_MOD_DELETE, NULL);
        if (ret != LDB_SUCCESS) {
            goto done;
        }
    }

    /* process memberuid */
    if (x->memuids) {
        if (x->orig_has_memberuid) {
            flags = LDB_FLAG_MOD_REPLACE;
        } else {
            flags = LDB_FLAG_MOD_ADD;
        }

        ret = ldb_msg_add(msg, x->memuids, flags);
        if (ret != LDB_SUCCESS) {
            goto done;
        }
    }
    else if (x->orig_has_memberuid) {
        ret = ldb_msg_add_empty(msg, DB_MEMBERUID, LDB_FLAG_MOD_DELETE, NULL);
        if (ret != LDB_SUCCESS) {
            goto done;
        }
    }

    ret = ldb_build_mod_req(&req, ldb, ctx, msg, NULL,
                            ctx, mbof_rcmp_mod_callback,
                            ctx->req);
    if (ret != LDB_SUCCESS) {
        goto done;
    }
    talloc_steal(req, msg);

    /* fire next call */
    return ldb_next_request(ctx->module, req);

done:
    /* all users and groups have been processed */
    return ldb_module_done(ctx->req, NULL, NULL, ret);
}

static int mbof_rcmp_mod_callback(struct ldb_request *req,
                                  struct ldb_reply *ares)
{
    struct ldb_context *ldb;
    struct mbof_rcmp_context *ctx;

    ctx = talloc_get_type(req->context, struct mbof_rcmp_context);
    ldb = ldb_module_get_ctx(ctx->module);

    if (!ares) {
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    }
    if (ares->error != LDB_SUCCESS) {
        return ldb_module_done(ctx->req,
                               ares->controls,
                               ares->response,
                               ares->error);
    }

    switch (ares->type) {
    case LDB_REPLY_ENTRY:
        ldb_debug(ldb, LDB_DEBUG_TRACE, "Got an entry on a non search op ?!");
        /* shouldn't happen */
        talloc_zfree(ares);
        return ldb_module_done(ctx->req, NULL, NULL,
                               LDB_ERR_OPERATIONS_ERROR);
    case LDB_REPLY_REFERRAL:
        /* ignore */
        talloc_zfree(ares);
        break;

    case LDB_REPLY_DONE:
        talloc_zfree(ares);

        /* update the next one */
        return mbof_rcmp_update(ctx);
    }

    return LDB_SUCCESS;
}



/* module init code */

static int memberof_init(struct ldb_module *module)
{
    struct ldb_context *ldb = ldb_module_get_ctx(module);
    int ret;

    /* set syntaxes for member and memberof so that comparisons in filters and
     * such are done right */
    ret = ldb_schema_attribute_add(ldb, DB_MEMBER, 0, LDB_SYNTAX_DN);
    ret = ldb_schema_attribute_add(ldb, DB_MEMBEROF, 0, LDB_SYNTAX_DN);

    return ldb_next_init(module);
}

const struct ldb_module_ops ldb_memberof_module_ops = {
    .name = "memberof",
    .init_context = memberof_init,
    .add = memberof_add,
    .modify = memberof_mod,
    .del = memberof_del,
};