2 * Copyright (c) 2012 Jiri Svoboda
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 * @brief Datagram reassembly.
38 #include <fibril_synch.h>
48 /** Datagram being reassembled.
50 * Uniquely identified by (source address, destination address, protocol,
51 * identification) per RFC 791 sec. 2.3 / Fragmentation.
55 /** List of fragments, @c reass_frag_t */
59 /** One datagram fragment */
65 /** Datagram map, list of reass_dgram_t */
66 static LIST_INITIALIZE(reass_dgram_map
);
67 /** Protects access to @c reass_dgram_map */
68 static FIBRIL_MUTEX_INITIALIZE(reass_dgram_map_lock
);
70 static reass_dgram_t
*reass_dgram_new(void);
71 static reass_dgram_t
*reass_dgram_get(inet_packet_t
*);
72 static errno_t
reass_dgram_insert_frag(reass_dgram_t
*, inet_packet_t
*);
73 static bool reass_dgram_complete(reass_dgram_t
*);
74 static void reass_dgram_remove(reass_dgram_t
*);
75 static errno_t
reass_dgram_deliver(reass_dgram_t
*);
76 static void reass_dgram_destroy(reass_dgram_t
*);
78 /** Queue packet for datagram reassembly.
80 * @param packet Packet
81 * @return EOK on success or ENOMEM.
83 errno_t
inet_reass_queue_packet(inet_packet_t
*packet
)
88 log_msg(LOG_DEFAULT
, LVL_DEBUG
, "inet_reass_queue_packet()");
90 fibril_mutex_lock(&reass_dgram_map_lock
);
92 /* Get existing or new datagram */
93 rdg
= reass_dgram_get(packet
);
95 /* Only happens when we are out of memory */
96 fibril_mutex_unlock(&reass_dgram_map_lock
);
97 log_msg(LOG_DEFAULT
, LVL_DEBUG
, "Allocation failed, packet dropped.");
101 /* Insert fragment into the datagram */
102 rc
= reass_dgram_insert_frag(rdg
, packet
);
106 /* Check if datagram is complete */
107 if (reass_dgram_complete(rdg
)) {
108 /* Remove it from the map */
109 reass_dgram_remove(rdg
);
110 fibril_mutex_unlock(&reass_dgram_map_lock
);
112 /* Deliver complete datagram */
113 rc
= reass_dgram_deliver(rdg
);
114 reass_dgram_destroy(rdg
);
118 fibril_mutex_unlock(&reass_dgram_map_lock
);
122 /** Get datagram reassembly structure for packet.
124 * @param packet Packet
125 * @return Datagram reassembly structure matching @a packet
127 static reass_dgram_t
*reass_dgram_get(inet_packet_t
*packet
)
129 assert(fibril_mutex_is_locked(&reass_dgram_map_lock
));
131 list_foreach(reass_dgram_map
, map_link
, reass_dgram_t
, rdg
) {
132 link_t
*f1_link
= list_first(&rdg
->frags
);
133 assert(f1_link
!= NULL
);
135 reass_frag_t
*f1
= list_get_instance(f1_link
, reass_frag_t
,
138 if ((inet_addr_compare(&f1
->packet
.src
, &packet
->src
)) &&
139 (inet_addr_compare(&f1
->packet
.dest
, &packet
->dest
)) &&
140 (f1
->packet
.proto
== packet
->proto
) &&
141 (f1
->packet
.ident
== packet
->ident
)) {
147 /* No existing reassembly structure. Create a new one. */
148 return reass_dgram_new();
151 /** Create new datagram reassembly structure.
153 * @return New datagram reassembly structure.
155 static reass_dgram_t
*reass_dgram_new(void)
159 rdg
= calloc(1, sizeof(reass_dgram_t
));
163 list_append(&rdg
->map_link
, &reass_dgram_map
);
164 list_initialize(&rdg
->frags
);
169 static reass_frag_t
*reass_frag_new(void)
173 frag
= calloc(1, sizeof(reass_frag_t
));
177 link_initialize(&frag
->dgram_link
);
182 static errno_t
reass_dgram_insert_frag(reass_dgram_t
*rdg
, inet_packet_t
*packet
)
188 assert(fibril_mutex_is_locked(&reass_dgram_map_lock
));
190 frag
= reass_frag_new();
192 /* Clone the packet */
194 data_copy
= malloc(packet
->size
);
195 if (data_copy
== NULL
) {
200 memcpy(data_copy
, packet
->data
, packet
->size
);
202 frag
->packet
= *packet
;
203 frag
->packet
.data
= data_copy
;
206 * XXX Make resource-consuming attacks harder, eliminate any duplicate
207 * data immediately. Possibly eliminate redundant packet headers.
211 * Insert into the list, which is sorted by offs member ascending.
214 link
= list_first(&rdg
->frags
);
215 while (link
!= NULL
) {
216 reass_frag_t
*qf
= list_get_instance(link
, reass_frag_t
,
219 if (qf
->packet
.offs
>= packet
->offs
)
222 link
= list_next(link
, &rdg
->frags
);
226 list_insert_after(&frag
->dgram_link
, link
);
228 list_append(&frag
->dgram_link
, &rdg
->frags
);
233 /** Check if datagram is complete.
235 * @param rdg Datagram reassembly structure
236 * @return @c true if complete, @c false if not
238 static bool reass_dgram_complete(reass_dgram_t
*rdg
)
240 reass_frag_t
*frag
, *prev
;
243 assert(fibril_mutex_is_locked(&reass_dgram_map_lock
));
244 assert(!list_empty(&rdg
->frags
));
246 link
= list_first(&rdg
->frags
);
247 assert(link
!= NULL
);
249 frag
= list_get_instance(link
, reass_frag_t
,
252 /* First fragment must be at offset zero */
253 if (frag
->packet
.offs
!= 0)
259 link
= list_next(link
, &rdg
->frags
);
263 /* Each next fragment must follow immediately or overlap */
264 frag
= list_get_instance(link
, reass_frag_t
, dgram_link
);
265 if (frag
->packet
.offs
> prev
->packet
.offs
+ prev
->packet
.size
)
268 /* No more fragments - datagram is complete */
269 if (!frag
->packet
.mf
)
278 /** Remove datagram from reassembly map.
280 * @param rdg Datagram reassembly structure
282 static void reass_dgram_remove(reass_dgram_t
*rdg
)
284 assert(fibril_mutex_is_locked(&reass_dgram_map_lock
));
285 list_remove(&rdg
->map_link
);
288 /** Deliver complete datagram.
290 * @param rdg Datagram reassembly structure.
292 static errno_t
reass_dgram_deliver(reass_dgram_t
*rdg
)
295 size_t fragoff_limit
;
302 * Potentially there could be something beyond the first packet
303 * that has !MF. Make sure we ignore that.
306 list_foreach(rdg
->frags
, dgram_link
, reass_frag_t
, cfrag
) {
307 if (!cfrag
->packet
.mf
) {
313 assert(frag
!= NULL
);
314 assert(!frag
->packet
.mf
);
316 dgram_size
= frag
->packet
.offs
+ frag
->packet
.size
;
318 /* Upper bound for fragment offset field */
319 fragoff_limit
= 1 << (FF_FRAGOFF_h
- FF_FRAGOFF_l
+ 1);
321 /* Verify that total size of datagram is within reasonable bounds */
322 if (dgram_size
> FRAG_OFFS_UNIT
* fragoff_limit
)
325 dgram
.data
= calloc(dgram_size
, 1);
326 if (dgram
.data
== NULL
)
329 /* XXX What if different fragments came from different link? */
330 dgram
.iplink
= frag
->packet
.link_id
;
331 dgram
.size
= dgram_size
;
332 dgram
.src
= frag
->packet
.src
;
333 dgram
.dest
= frag
->packet
.dest
;
334 dgram
.tos
= frag
->packet
.tos
;
335 proto
= frag
->packet
.proto
;
337 /* Pull together data from individual fragments */
341 list_foreach(rdg
->frags
, dgram_link
, reass_frag_t
, cfrag
) {
344 cb
= max(doffs
, cfrag
->packet
.offs
);
345 ce
= min(dgram_size
, cfrag
->packet
.offs
+ cfrag
->packet
.size
);
348 memcpy(dgram
.data
+ cb
,
349 cfrag
->packet
.data
+ cb
- cfrag
->packet
.offs
,
353 if (!cfrag
->packet
.mf
)
357 rc
= inet_recv_dgram_local(&dgram
, proto
);
362 /** Destroy datagram reassembly structure.
364 * @param rdg Datagram reassembly structure.
366 static void reass_dgram_destroy(reass_dgram_t
*rdg
)
368 while (!list_empty(&rdg
->frags
)) {
369 link_t
*flink
= list_first(&rdg
->frags
);
370 reass_frag_t
*frag
= list_get_instance(flink
, reass_frag_t
,
373 list_remove(&frag
->dgram_link
);
374 free(frag
->packet
.data
);