doxygen
[oweals/gnunet.git] / src / lockmanager / gnunet-service-lockmanager.c
1 /*
2   This file is part of GNUnet.
3   (C) 2012 Christian Grothoff (and other contributing authors)
4
5   GNUnet is free software; you can redistribute it and/or modify
6   it under the terms of the GNU General Public License as published
7   by the Free Software Foundation; either version 2, or (at your
8   option) any later version.
9
10   GNUnet is distributed in the hope that it will be useful, but
11   WITHOUT ANY WARRANTY; without even the implied warranty of
12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   General Public License for more details.
14
15   You should have received a copy of the GNU General Public License
16   along with GNUnet; see the file COPYING.  If not, write to the
17   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18   Boston, MA 02111-1307, USA.
19 */
20
21 /**
22  * @file lockmanager/gnunet-service-lockmanager.c
23  * @brief implementation of the LOCKMANAGER service
24  * @author Sree Harsha Totakura
25  */
26
27 #include "platform.h"
28 #include "gnunet_common.h"
29 #include "gnunet_container_lib.h"
30 #include "gnunet_protocols.h"
31 #include "gnunet_service_lib.h"
32 #include "gnunet_server_lib.h"
33
34 #include "lockmanager.h"
35
36
37 #define LOG(kind,...)                           \
38   GNUNET_log (kind, __VA_ARGS__)
39
40 #define TIME_REL_MINS(min)                                      \
41   GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, min)
42
43 #define TIMEOUT TIME_REL_MINS(3)
44
45
46 /**
47  * Doubly linked list of clients having connections to us
48  */
49 struct ClientList;
50
51
52 /**
53  * Doubly linked list of clients waiting for a lock
54  */
55 struct WaitList
56 {
57   /**
58    * The next client structure
59    */
60   struct WaitList *next;
61   
62   /**
63    * The prev client structure
64    */
65   struct WaitList *prev;
66
67   /**
68    * Pointer to the client
69    */
70   struct ClientList *cl_entry;
71 };
72
73
74 /**
75  * Structure representing a Lock
76  */
77 struct Lock
78 {
79   /**
80    * List head of clients waiting for this lock
81    */
82   struct WaitList *wl_head;
83
84   /**
85    * List tail of clients waiting for this lock
86    */
87   struct WaitList *wl_tail;
88
89   /**
90    * The client which is currently holding this lock
91    */
92   struct ClientList *cl_entry;
93
94   /**
95    * The name of the locking domain this lock belongs to
96    */
97   char *domain_name;
98
99   /**
100    * The number of this lock
101    */
102   uint32_t lock_num;
103 };
104
105
106 /**
107  * A Lock element for a doubly linked list
108  */
109 struct LockList
110 {
111   /**
112    * The next element pointer
113    */
114   struct LockList *next;
115
116   /**
117    * Pointer to the previous element
118    */
119   struct LockList *prev;
120
121   /**
122    * Pointer to the Lock
123    */
124   struct Lock *lock;
125 };
126
127
128 /**
129  * Doubly linked list of clients having connections to us
130  */
131 struct ClientList
132 {
133
134   /**
135    * The next client structure
136    */
137   struct ClientList *next;
138
139   /**
140    * The previous client structure
141    */
142   struct ClientList *prev;
143
144   /**
145    * Head of the doubly linked list of the currently held locks by this client
146    */
147   struct LockList *ll_head;
148
149   /**
150    * Tail of the doubly linked list of the currently held locks by this client
151    */
152   struct LockList *ll_tail;
153
154   /**
155    * Pointer to the client
156    */
157   struct GNUNET_SERVER_Client *client;
158 };
159
160
161 /**
162  * Map of lock-keys to the 'struct LockList' entry for the key.
163  */
164 static struct GNUNET_CONTAINER_MultiHashMap *lock_map;
165
166 /**
167  * Head of the doubly linked list of clients currently connected
168  */
169 static struct ClientList *cl_head;
170
171 /**
172  * Tail of the doubly linked list of clients currently connected
173  */
174 static struct ClientList *cl_tail;
175
176
177 /**
178  * Get the key for the given lock in the 'lock_map'.
179  *
180  * @param domain_name
181  * @param lock_number
182  * @param key set to the key
183  */
184 static void
185 get_key (const char *domain_name,
186          uint32_t lock_number,
187          struct GNUNET_HashCode *key)
188 {
189   uint32_t *last_32;
190
191   GNUNET_CRYPTO_hash (domain_name,
192                       strlen (domain_name),
193                       key);
194   last_32 = (uint32_t *) key;
195   *last_32 ^= lock_number;
196 }
197
198
199 /**
200  * Function to search for a lock in the global lock hashmap
201  *
202  * @param domain_name the name of the locking domain
203  * @param lock_num the number of the lock
204  * @return the lock if found; NULL if not
205  */
206 static struct Lock *
207 find_lock (const char *domain_name,
208            const uint32_t lock_num)
209               
210 {
211   struct Lock *matched_lock;
212   struct GNUNET_HashCode key;
213
214   matched_lock = NULL;
215   int match_lock (void *cls,
216                   const GNUNET_HashCode *key,
217                   void *value)
218   {
219     matched_lock = value;
220
221     if ((lock_num == matched_lock->lock_num)
222         && (0 == strcmp (domain_name, matched_lock->domain_name)))
223       return GNUNET_NO;
224     matched_lock = NULL;
225     return GNUNET_YES;
226   }
227   get_key (domain_name, lock_num, &key);
228   GNUNET_CONTAINER_multihashmap_get_multiple (lock_map,
229                                               &key,
230                                               &match_lock,
231                                               NULL);
232   return matched_lock;
233 }
234
235
236 /**
237  * Adds a lock to the global lock hashmap
238  *
239  * @param domain_name the name of the lock's locking domain
240  * @param lock_num the lock number
241  * @return pointer to the lock structure which is added to lock map
242  */
243 static struct Lock *
244 add_lock (const char *domain_name, 
245           uint32_t lock_num)
246 {
247   struct Lock *lock;
248   struct GNUNET_HashCode key;
249   size_t domain_name_len;
250
251   lock = GNUNET_malloc (sizeof (struct Lock));
252   domain_name_len = strlen (domain_name) + 1;
253   lock->domain_name = GNUNET_malloc (domain_name_len);
254   strncpy (lock->domain_name, domain_name, domain_name_len);
255   lock->lock_num = lock_num;
256   get_key (domain_name, lock_num, &key);
257   LOG (GNUNET_ERROR_TYPE_DEBUG,
258        "Adding a lock with num: %d and domain: %s to the lock map\n",
259        lock->lock_num, lock->domain_name);
260   GNUNET_CONTAINER_multihashmap_put (lock_map,
261                                      &key,
262                                      lock,
263                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
264   return lock;
265 }
266
267
268 /**
269  * Removes a lock from the lock map
270  *
271  * @param lock the lock to remove
272  */
273 static void
274 remove_lock (struct Lock *lock)
275 {
276   struct GNUNET_HashCode key;
277
278   get_key (lock->domain_name,
279            lock->lock_num,
280            &key);
281   LOG (GNUNET_ERROR_TYPE_DEBUG,
282        "Removing lock with num: %u, domain: %s from lock map\n",
283        lock->lock_num, lock->domain_name);
284   GNUNET_assert (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove
285                  (lock_map, &key, lock));
286   GNUNET_free (lock->domain_name);
287   GNUNET_free (lock);
288 }
289
290
291 /**
292  * Find the LockList entry corresponding to the given Lock in a ClientList
293  * entry
294  *
295  * @param cl_entry the ClientList entry whose lock list has to be searched
296  * @param lock the lock which has to be matched
297  * @return the matching LockList entry; NULL if no match is found
298  */
299 static struct LockList *
300 cl_ll_find_lock (struct ClientList *cl_entry,
301                  const struct Lock *lock)
302 {
303   struct LockList *ll_entry;
304
305   for (ll_entry = cl_entry->ll_head;
306        NULL != ll_entry; ll_entry = ll_entry->next)
307   {
308     if (lock == ll_entry->lock)
309       return ll_entry;
310   }
311   return NULL;
312 }
313
314
315 /**
316  * Function to append a lock to the lock list of a ClientList entry
317  *
318  * @param cl_entry the client which currently owns this lock
319  * @param lock the lock to be added to the cl_entry's lock list
320  */
321 static void
322 cl_ll_add_lock (struct ClientList *cl_entry,
323                 struct Lock *lock)
324 {
325   struct LockList *ll_entry;
326
327   ll_entry = GNUNET_malloc (sizeof (struct LockList));
328   ll_entry->lock = lock;
329   LOG (GNUNET_ERROR_TYPE_DEBUG,
330        "Adding a lock with num: %u and domain: %s to lock list\n",
331        lock->lock_num, lock->domain_name);
332   GNUNET_CONTAINER_DLL_insert_tail (cl_entry->ll_head,
333                                     cl_entry->ll_tail,
334                                     ll_entry);
335 }
336
337
338 /**
339  * Function to delete a lock from the lock list of the given ClientList entry
340  *
341  * @param cl_entry the ClientList entry
342  * @param ll_entry the LockList entry to be deleted
343  */
344 static void
345 cl_ll_remove_lock (struct ClientList *cl_entry,
346                    struct LockList *ll_entry)
347 {
348   LOG (GNUNET_ERROR_TYPE_DEBUG,
349        "Removing lock with num: %u, domain: %s from lock list of a client\n",
350        ll_entry->lock->lock_num,
351        ll_entry->lock->domain_name);
352   GNUNET_assert (NULL != cl_entry->ll_head);
353   GNUNET_CONTAINER_DLL_remove (cl_entry->ll_head,
354                                cl_entry->ll_tail,
355                                ll_entry);
356   GNUNET_free (ll_entry);
357 }
358
359
360 /**
361  * Find a WaitList entry in the waiting list of a lock
362  *
363  * @param lock the lock whose wait list has to be searched
364  * @param cl_entry the ClientList entry to be searched
365  * @return the WaitList entry matching the given cl_entry; NULL if not match
366  *           was found
367  */
368 static struct WaitList *
369 lock_wl_find (const struct Lock *lock,
370               const struct ClientList *cl_entry)
371 {
372   struct WaitList *wl_entry;
373
374   for (wl_entry = lock->wl_head;
375        NULL != wl_entry; 
376        wl_entry = wl_entry->next)
377   {
378     if (cl_entry == wl_entry->cl_entry)
379       return wl_entry;
380   }
381   return NULL;
382 }
383
384
385 /**
386  * Add a client to the wait list of given lock
387  *
388  * @param lock the lock list entry of a lock
389  * @param cl_entry the client to queue for the lock's wait list
390  */
391 static void
392 lock_wl_add_client (struct Lock *lock,
393                     struct ClientList *cl_entry)
394 {
395   struct WaitList *wl_entry;
396
397   LOG (GNUNET_ERROR_TYPE_DEBUG,
398        "Adding a client to lock's wait list (lock num: %u, domain: %s)\n",
399        lock->lock_num,
400        lock->domain_name);
401   wl_entry = GNUNET_malloc (sizeof (struct WaitList));
402   wl_entry->cl_entry = cl_entry;
403   GNUNET_CONTAINER_DLL_insert_tail (lock->wl_head,
404                                     lock->wl_tail,
405                                     wl_entry);
406 }
407
408
409 /**
410  * Remove an entry from the wait list of the given lock
411  *
412  * @param lock the lock
413  * @param wl_entry the wait list entry to be removed
414  */
415 static void
416 lock_wl_remove (struct Lock *lock,
417                 struct WaitList *wl_entry)
418 {
419   LOG (GNUNET_ERROR_TYPE_DEBUG,
420        "Removing client from wait list of lock with num: %u, domain: %s\n",
421        lock->lock_num, lock->domain_name);
422   GNUNET_CONTAINER_DLL_remove (lock->wl_head,
423                                lock->wl_tail,
424                                wl_entry);
425   GNUNET_free (wl_entry);
426 }
427
428
429 /**
430  * Search for a client in the client list
431  *
432  * @param client the client to be searched for
433  * @return the ClientList entry; NULL if the client is not found
434  */
435 static struct ClientList *
436 cl_find_client (const struct GNUNET_SERVER_Client *client)                
437 {
438   struct ClientList *current;
439
440   for (current = cl_head; NULL != current; current = current->next)
441     if (client == current->client)
442       return current;
443   return NULL;
444 }
445
446
447 /**
448  * Append a client to the client list
449  *
450  * @param client the client to be appended to the list
451  * @return the client list entry which is added to the client list
452  */
453 static struct ClientList *
454 cl_add_client (struct GNUNET_SERVER_Client *client)
455 {
456   struct ClientList *new_client;
457   
458   LOG (GNUNET_ERROR_TYPE_DEBUG,
459        "Adding a client to the client list\n");
460   new_client = GNUNET_malloc (sizeof (struct ClientList));
461   GNUNET_SERVER_client_keep (client);
462   new_client->client = client;
463   GNUNET_CONTAINER_DLL_insert_tail (cl_head,
464                                     cl_tail,
465                                     new_client);
466   return new_client;
467 }
468
469
470 /**
471  * Delete the given client from the client list
472  *
473  * @param cl_entry the client list entry to delete
474  */
475 static void
476 cl_remove_client (struct ClientList *cl_entry)
477 {
478   LOG (GNUNET_ERROR_TYPE_DEBUG,
479        "Removing a client from the client list\n");
480   GNUNET_SERVER_client_drop (cl_entry->client);
481   GNUNET_CONTAINER_DLL_remove (cl_head,
482                                cl_tail,
483                                cl_entry);
484   GNUNET_free (cl_entry);
485 }
486
487
488 /**
489  * Transmit notify for sending message to client
490  *
491  * @param cls the message to send
492  * @param size number of bytes available in buf
493  * @param buf where the callee should write the message
494  * @return number of bytes written to buf
495  */
496 static size_t 
497 transmit_notify (void *cls, size_t size, void *buf)
498 {
499   struct GNUNET_LOCKMANAGER_Message *msg = cls;
500   uint16_t msg_size;
501
502   if ((0 == size) || (NULL == buf))
503   {
504     /* FIXME: Timed out -- requeue? */
505     return 0;
506   }
507   msg_size = ntohs (msg->header.size);
508   GNUNET_assert (size >= msg_size);
509   memcpy (buf, msg, msg_size);
510   GNUNET_free (msg);
511   LOG (GNUNET_ERROR_TYPE_DEBUG,
512        "Message of size %u sent\n", msg_size);
513   return msg_size;
514 }
515
516
517 /**
518  * Send SUCCESS message to the client
519  *
520  * @param client the client to which the message has to be sent
521  * @param domain_name the locking domain of the successfully acquried lock
522  * @param lock_num the number of the successfully acquired lock
523  */
524 static void
525 send_success_msg (struct GNUNET_SERVER_Client *client,
526                   const char *domain_name,
527                   int lock_num)
528 {
529   struct GNUNET_LOCKMANAGER_Message *reply;
530   size_t domain_name_len;
531   uint16_t reply_size;
532
533   domain_name_len = strlen (domain_name) + 1;
534   reply_size = sizeof (struct GNUNET_LOCKMANAGER_Message) + domain_name_len;
535   reply = GNUNET_malloc (reply_size);
536   reply->header.size = htons (reply_size);
537   reply->header.type = htons (GNUNET_MESSAGE_TYPE_LOCKMANAGER_SUCCESS);
538   reply->lock = htonl (lock_num);
539   strncpy ((char *) &reply[1], domain_name, domain_name_len);
540   LOG (GNUNET_ERROR_TYPE_DEBUG,
541        "Sending SUCCESS message for lock with num: %u, domain: %s\n",
542        lock_num, domain_name);
543   GNUNET_SERVER_notify_transmit_ready (client,
544                                        reply_size,
545                                        TIMEOUT,
546                                        &transmit_notify,
547                                        reply);
548 }
549
550
551 /**
552  * Handler for GNUNET_MESSAGE_TYPE_LOCKMANAGER_ACQUIRE
553  *
554  * @param cls NULL
555  * @param client the client sending this message
556  * @param message GNUNET_MESSAGE_TYPE_LOCKMANAGER_ACQUIRE message
557  */
558 static void
559 handle_acquire (void *cls,
560                 struct GNUNET_SERVER_Client *client,
561                 const struct GNUNET_MessageHeader *message)
562 {
563   const struct GNUNET_LOCKMANAGER_Message *request;
564   const char *domain_name;
565   struct Lock *lock;
566   struct ClientList *cl_entry;
567   uint32_t lock_num;
568   uint16_t msize;
569
570   msize = htons (message->size);
571   if (msize <= sizeof (struct GNUNET_LOCKMANAGER_Message))
572   {
573     GNUNET_break (0);
574     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
575     return;
576   }
577   request = (struct GNUNET_LOCKMANAGER_Message *) message;
578   domain_name = (const char *) &request[1];
579   msize -= sizeof (struct GNUNET_LOCKMANAGER_Message);
580   if ('\0' != domain_name[msize])
581   {
582     GNUNET_break (0);
583     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
584     return;
585   }
586   lock_num = ntohl (request->lock);
587   LOG (GNUNET_ERROR_TYPE_DEBUG,
588        "Received an ACQUIRE message for lock num: %u domain: %s\n",
589        lock_num, domain_name);
590   if (NULL == (cl_entry = cl_find_client (client))) 
591     cl_entry = cl_add_client (client); /* Add client if not in client list */
592   if (NULL != (lock = find_lock (domain_name,lock_num)))
593   {
594     if (lock->cl_entry == cl_entry)
595     {                         /* Client is requesting a lock it already owns */
596       GNUNET_break (0);
597       GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
598       return;
599     }
600     lock_wl_add_client (lock, cl_entry);
601     cl_ll_add_lock (cl_entry, lock);
602   }
603   else                          /* Lock not present */
604   {
605     lock = add_lock (domain_name, lock_num);
606     lock->cl_entry = cl_entry;
607     cl_ll_add_lock (cl_entry, lock);
608     send_success_msg (cl_entry->client, domain_name, lock_num);
609   }
610   GNUNET_SERVER_receive_done (client, GNUNET_OK);
611 }
612
613
614 /**
615  * This function gives the lock to the first client in the wait list of the
616  * lock. If no clients are currently waiting for this lock, the lock is then
617  * destroyed.
618  *
619  * @param lock the lock which has to be processed for release
620  */
621 static void
622 process_lock_release (struct Lock *lock)
623 {
624   struct WaitList *wl_entry;
625
626   LOG (GNUNET_ERROR_TYPE_DEBUG,
627        "Processing lock release for lock with num: %u, domain: %s\n",
628        lock->lock_num, lock->domain_name);
629   wl_entry = lock->wl_head;
630   if (NULL == wl_entry)
631   {
632     remove_lock (lock);   /* No clients waiting for this lock - delete */
633     return;
634   }
635   LOG (GNUNET_ERROR_TYPE_DEBUG,
636        "Giving lock to a client from wait list\n");
637   lock->cl_entry = wl_entry->cl_entry;
638   cl_ll_add_lock (wl_entry->cl_entry, lock);
639   lock_wl_remove(lock, wl_entry);
640   send_success_msg (lock->cl_entry->client,
641                     lock->domain_name,
642                     lock->lock_num);
643   return;
644 }
645
646
647 /**
648  * Handle for GNUNET_MESSAGE_TYPE_LOCKMANAGER_RELEASE
649  *
650  * @param cls NULL
651  * @param client the client sending this message
652  * @param message the LOCKMANAGER_RELEASE message
653  */
654 static void
655 handle_release (void *cls,
656                 struct GNUNET_SERVER_Client *client,
657                 const struct GNUNET_MessageHeader *message)
658 {
659   const struct GNUNET_LOCKMANAGER_Message *request;
660   struct ClientList *cl_entry;
661   struct WaitList *wl_entry;
662   struct LockList *ll_entry;
663   const char *domain_name;
664   struct Lock *lock;
665   uint32_t lock_num;
666   uint16_t msize;
667
668   msize = ntohs (message->size);
669   if (msize <= sizeof (struct GNUNET_LOCKMANAGER_Message))
670   { 
671     GNUNET_break (0);
672     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
673     return;
674   }
675   request = (const struct GNUNET_LOCKMANAGER_Message *) message;
676   domain_name = (const char *) &request[1];
677   msize -= sizeof (struct GNUNET_LOCKMANAGER_Message);
678   if ('\0' != domain_name[msize-1])
679   {
680     GNUNET_break (0);
681     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
682     return;
683   
684
685   }
686   lock_num = ntohl (request->lock);
687   LOG (GNUNET_ERROR_TYPE_DEBUG,
688        "Received RELEASE message for lock with num: %d, domain: %s\n",
689        lock_num, domain_name);
690   if (NULL == (cl_entry = cl_find_client (client)))
691   {
692     GNUNET_break(0);
693     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
694     return;
695   }
696   lock = find_lock (domain_name, lock_num);
697   if(NULL == lock)
698   {    
699     GNUNET_break (0);
700     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
701     return;
702   }
703   if (NULL == (ll_entry = cl_ll_find_lock (cl_entry, lock)))
704   {
705     GNUNET_break (0);
706     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
707     return;
708   }
709   cl_ll_remove_lock (cl_entry, ll_entry);
710   if (cl_entry == lock->cl_entry)
711   {
712     process_lock_release (lock);
713     GNUNET_SERVER_receive_done (client, GNUNET_OK);
714     return;
715   }
716   /* remove 'client' from wait list (check that it is not there...) */
717   if (NULL != (wl_entry = lock_wl_find (lock, cl_entry)))
718   {
719     lock_wl_remove (lock, wl_entry);
720   }
721   GNUNET_SERVER_receive_done (client, GNUNET_OK);
722 }
723
724
725 /**
726  * Callback for client disconnect
727  *
728  * @param cls NULL
729  * @param client the client which has disconnected
730  */
731 static void
732 client_disconnect_cb (void *cls, struct GNUNET_SERVER_Client *client)
733 {
734   struct ClientList *cl_entry;
735   struct LockList *ll_entry;
736
737   if (NULL == client)
738     return;
739   LOG (GNUNET_ERROR_TYPE_DEBUG,
740        "A client has been disconnected -- freeing its locks and resources\n"); 
741   cl_entry = cl_find_client (client);
742   if (NULL == cl_entry)
743     return;
744   while (NULL != (ll_entry = cl_entry->ll_head))
745   {
746     process_lock_release (ll_entry->lock);
747     cl_ll_remove_lock (cl_entry, ll_entry);
748   }
749   cl_remove_client (cl_entry);
750 }
751
752
753 /**
754  * Lock manager setup
755  *
756  * @param cls closure
757  * @param server the initialized server
758  * @param cfg configuration to use
759  */
760 static void 
761 lockmanager_run (void *cls,
762                  struct GNUNET_SERVER_Handle * server,
763                  const struct GNUNET_CONFIGURATION_Handle *cfg)
764 {
765   static const struct GNUNET_SERVER_MessageHandler message_handlers[] =
766     {
767       {&handle_acquire, NULL, GNUNET_MESSAGE_TYPE_LOCKMANAGER_ACQUIRE, 0},
768       {&handle_release, NULL, GNUNET_MESSAGE_TYPE_LOCKMANAGER_RELEASE, 0},
769       {NULL}
770     };
771   GNUNET_SERVER_add_handlers (server,
772                               message_handlers);
773   GNUNET_SERVER_disconnect_notify (server,
774                                    &client_disconnect_cb,
775                                    NULL);
776   lock_map = GNUNET_CONTAINER_multihashmap_create (30);
777 }
778
779
780 /**
781  * The starting point of execution
782  */
783 int main (int argc, char *const *argv)
784 {
785   return
786     (GNUNET_OK ==
787      GNUNET_SERVICE_run (argc,
788                          argv,
789                          "lockmanager",
790                          GNUNET_SERVICE_OPTION_NONE,
791                          &lockmanager_run,
792                          NULL)) ? 0 : 1;
793 }