9f213c7eed0aef80848d10ca81793b57f73c6b7c
[olsrd.git] / lib / pud / src / dedup.c
1 #include "dedup.h"
2
3 /* Plugin includes */
4
5 /* OLSR includes */
6 #include "olsr.h"
7
8 /* System includes */
9 #include <assert.h>
10 #include <pthread.h>
11 #include <stddef.h>
12
13 #ifdef PUD_DUMP_DEDUP
14 #include <arpa/inet.h>
15 #endif
16
17 /* Defines */
18
19 #define LISTSIZE(x)                     ((x)->entriesMaxCount) /* always valid */
20 #define NEWESTINDEX(x)          ((x)->newestEntryIndex) /* always valid */
21 #define WRAPINDEX(x, i)         ((i) % LISTSIZE(x)) /* always valid for i>=0 */
22 #define INCOMINGINDEX(x)        WRAPINDEX(x, (NEWESTINDEX(x) + LISTSIZE(x) - 1)) /* always valid */
23
24 /**
25  Initialise the de-duplication list: allocate memory for the entries and
26  reset fields.
27
28  @param deDupList
29  The de-duplication list
30  @param maxEntries
31  The maximum number of entries in the list (the number of messages that should
32  be tracked)
33
34  @return
35  - false on failure
36  - true otherwise
37  */
38 bool initDeDupList(DeDupList * deDupList, unsigned long long maxEntries) {
39         pthread_mutexattr_t attr;
40         void * p;
41
42         if (deDupList == NULL) {
43                 return false;
44         }
45         if (maxEntries < 1) {
46                 return false;
47         }
48
49         if (pthread_mutexattr_init(&attr)) {
50                 return false;
51         }
52         if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE_NP)) {
53                 return false;
54         }
55         if (pthread_mutex_init(&deDupList->mutex, &attr)) {
56                 return false;
57         }
58
59         p = olsr_malloc(maxEntries * sizeof(DeDupEntry),
60                         "DeDupEntry entries for DeDupList (PUD)");
61         if (p == NULL) {
62                 return false;
63         }
64
65         deDupList->entriesMaxCount = maxEntries;
66         deDupList->entries = p;
67
68         deDupList->entriesCount = 0;
69         deDupList->newestEntryIndex = 0;
70
71         return true;
72 }
73
74 /**
75  Clean up the de-duplication list: free memory and reset fields.
76
77  @param deDupList
78  The de-duplication list
79  */
80 void destroyDeDupList(DeDupList * deDupList) {
81         assert (deDupList != NULL);
82
83         (void) pthread_mutex_lock(&deDupList->mutex);
84
85         if (deDupList->entries != NULL) {
86                 free(deDupList->entries);
87                 deDupList->entries = NULL;
88         }
89
90         deDupList->entriesMaxCount = 0;
91
92         deDupList->entriesCount = 0;
93         deDupList->newestEntryIndex = 0;
94
95         (void) pthread_mutex_unlock(&deDupList->mutex);
96
97         pthread_mutex_destroy(&deDupList->mutex);
98 }
99
100 /**
101  Add a new (incoming) message to the de-duplication list
102
103  @param deDupList
104  The de-duplication list
105  @param olsrMessage
106  The message
107  */
108 void addToDeDup(DeDupList * deDupList, union olsr_message *olsrMessage) {
109         unsigned long long incomingIndex;
110         DeDupEntry * newEntry;
111
112         assert (deDupList != NULL);
113
114         (void) pthread_mutex_lock(&deDupList->mutex);
115
116         incomingIndex = INCOMINGINDEX(deDupList);
117         newEntry = &deDupList->entries[incomingIndex];
118
119 #ifdef PUD_DUMP_DEDUP
120         olsr_printf(0, "addToDeDup: entriesCount=%llu, newestEntryIndex=%llu,"
121                         " incomingIndex=%llu (before)\n", deDupList->entriesCount,
122                         deDupList->newestEntryIndex, INCOMINGINDEX(deDupList));
123 #endif
124
125         memset(newEntry, 0, sizeof(DeDupEntry));
126         if (olsr_cnf->ip_version == AF_INET) {
127                 newEntry->seqno = olsrMessage->v4.seqno;
128                 newEntry->originator.v4.s_addr = olsrMessage->v4.originator;
129         } else {
130                 newEntry->seqno = olsrMessage->v6.seqno;
131                 newEntry->originator.v6 = olsrMessage->v6.originator;
132         }
133
134         deDupList->newestEntryIndex = incomingIndex;
135         if (deDupList->entriesCount < deDupList->entriesMaxCount) {
136                 deDupList ->entriesCount++;
137         }
138
139 #ifdef PUD_DUMP_DEDUP
140         {
141                 char addr[64];
142                 olsr_printf(0, "addToDeDup: added seqno %u from %s\n", newEntry->seqno,
143                                 inet_ntop(olsr_cnf->ip_version,
144                                                 &newEntry->originator,
145                                                 &addr[0],sizeof(addr)));
146                 olsr_printf(0, "addToDeDup: entriesCount=%llu, newestEntryIndex=%llu,"
147                                 " incomingIndex=%llu (after)\n\n", deDupList->entriesCount,
148                                 deDupList->newestEntryIndex, INCOMINGINDEX(deDupList));
149         }
150 #endif
151
152         (void) pthread_mutex_unlock(&deDupList->mutex);
153 }
154
155 /**
156  Determines whether a new (incoming) message is already in the de-duplication
157  list
158
159  @param deDupList
160  The de-duplication list
161  @param olsrMessage
162  The message
163
164  @return
165  - true when the message is already in the list
166  - false otherwise
167  */
168 bool isInDeDupList(DeDupList * deDupList, union olsr_message *olsrMessage) {
169         bool retval = false;
170         unsigned long long iteratedIndex;
171         unsigned long long count;
172
173         (void) pthread_mutex_lock(&deDupList->mutex);
174
175         iteratedIndex = NEWESTINDEX(deDupList);
176         count = deDupList->entriesCount;
177
178 #ifdef PUD_DUMP_DEDUP
179         olsr_printf(0, "isInDeDupList: count=%llu, iteratedIndex=%llu"
180                         " maxCount=%llu (iteration start)\n", count, iteratedIndex,
181                         deDupList->entriesMaxCount);
182 #endif
183
184         /* we iterate from newest until oldest: we have a higher probability to
185          * match on the newest entries */
186
187         while (count > 0) {
188                 DeDupEntry * iteratedEntry = &deDupList->entries[iteratedIndex];
189
190 #ifdef PUD_DUMP_DEDUP
191                 olsr_printf(0, "isInDeDupList: count=%llu, iteratedIndex=%llu"
192                                 " (iteration)\n", count, iteratedIndex);
193 #endif
194
195                 if (olsr_cnf->ip_version == AF_INET) {
196 #ifdef PUD_DUMP_DEDUP
197                         {
198                                 char iteratedAddr[64];
199                                 char olsrMessageAddr[64];
200
201                                 olsr_printf(0, "isInDeDupList: iterated.seqno %u ==?"
202                                                 " olsrMessage.seqno %u\n", iteratedEntry->seqno,
203                                                 olsrMessage->v4.seqno);
204                                 olsr_printf(0, "isInDeDupList: iterated.addr %s ==?"
205                                                 " olsrMessage.addr %s\n", inet_ntop(olsr_cnf->ip_version,
206                                                                 &iteratedEntry->originator.v4,
207                                                                 &iteratedAddr[0],sizeof(iteratedAddr)),
208                                                                 inet_ntop(olsr_cnf->ip_version,
209                                                                 &olsrMessage->v4.originator,
210                                                                 &olsrMessageAddr[0],sizeof(olsrMessageAddr)));
211                         }
212 #endif
213                         if ((iteratedEntry->seqno == olsrMessage->v4.seqno) && (memcmp(
214                                         &iteratedEntry->originator.v4, &olsrMessage->v4.originator,
215                                         sizeof(iteratedEntry->originator.v4))) == 0) {
216                                 retval = true;
217                                 break;
218                         }
219                 } else {
220 #ifdef PUD_DUMP_DEDUP
221                         {
222                                 char iteratedAddr[64];
223                                 char olsrMessageAddr[64];
224
225                                 olsr_printf(0, "isInDeDupList: iterated.seqno %u ==?"
226                                                 " olsrMessage.seqno %u\n", iteratedEntry->seqno,
227                                                 olsrMessage->v6.seqno);
228                                 olsr_printf(0, "isInDeDupList: iterated.addr %s ==?"
229                                                 " olsrMessage.addr %s\n", inet_ntop(olsr_cnf->ip_version,
230                                                                 &iteratedEntry->originator.v6,
231                                                                 &iteratedAddr[0],sizeof(iteratedAddr)),
232                                                                 inet_ntop(olsr_cnf->ip_version,
233                                                                 &olsrMessage->v6.originator,
234                                                                 &olsrMessageAddr[0],sizeof(olsrMessageAddr)));
235                         }
236 #endif
237                         if ((iteratedEntry->seqno == olsrMessage->v6.seqno) && (memcmp(
238                                         &iteratedEntry->originator.v6, &olsrMessage->v6.originator,
239                                         sizeof(iteratedEntry->originator.v6)) == 0)) {
240                                 retval = true;
241                                 break;
242                         }
243                 }
244
245                 iteratedIndex = WRAPINDEX(deDupList, iteratedIndex + 1); /* go the the next older entry */
246                 count--;
247         }
248
249 #ifdef PUD_DUMP_DEDUP
250         olsr_printf(0,"isInDeDupList: result = %s\n\n", retval ? "true" : "false");
251 #endif
252
253         (void) pthread_mutex_unlock(&deDupList->mutex);
254
255         return retval;
256 }