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