acac9d72aaaaf9a15e68ad17e2a206f89d24f695
1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
4 * This program is free software: you can redistribute it and/or modify it
5 * under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation, either version 2.1 of the License, or (at
7 * your option) any later version.
9 * This program is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
12 * License for more details.
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
22 #include <arpa/inet.h>
33 #include "data_structures.h"
36 // TCP sequence numbers use clock arithmetic, these comparison functions take
38 #define SEQ_LT(a,b) ((int32_t)((a)-(b)) < 0)
39 #define SEQ_LEQ(a,b) ((int32_t)((a)-(b)) <= 0)
40 #define SEQ_GT(a,b) ((int32_t)((a)-(b)) > 0)
41 #define SEQ_GEQ(a,b) ((int32_t)((a)-(b)) >= 0)
43 const char* const approxNames
[]= {
45 [ACCURATE
]= "Accurate",
46 [APPROXIMATE
]= "Approximate",
47 [INCOMPLETE
]= "Incomplete",
54 * Compare two ConnectionKey structures
57 * true if each field of the structure is equal
60 bool connectionKeyEqual(const ConnectionKey
* const a
, const
61 ConnectionKey
* const b
)
63 if (a
->saddr
== b
->saddr
&& a
->daddr
== b
->daddr
&& a
->source
== b
->source
64 && a
->dest
== b
->dest
)
76 * Check if a packet is an acknowledge of another packet.
79 * ackSegment packet that is the confirmation
80 * ackedSegment packet that contains the original data, both packets have to
81 * come from the same direction of the same connection. Both
82 * messages have to contain TCP events.
84 bool isAcking(const Message
* const ackSegment
, const Message
* const
87 g_assert(ackSegment
->inE
->type
== TCP
);
88 g_assert(ackSegment
->outE
->type
== TCP
);
90 if (SEQ_GT(ackSegment
->inE
->event
.tcpEvent
->segmentKey
->ack_seq
,
91 ackedSegment
->inE
->event
.tcpEvent
->segmentKey
->seq
))
103 * Convert an IP address from 32 bit form to dotted quad
106 * str: A preallocated string of length >= 16
109 void convertIP(char* const str
, const uint32_t addr
)
111 strcpy(str
, inet_ntoa((struct in_addr
) {.s_addr
= addr
}));
116 * Print the content of a TCP Message structure
118 void printTCPSegment(const Message
* const segment
)
120 char saddr
[16], daddr
[16];
121 SegmentKey
* segmentKey
;
123 g_assert(segment
->inE
->type
== TCP
);
124 g_assert(segment
->inE
->event
.tcpEvent
->segmentKey
==
125 segment
->outE
->event
.tcpEvent
->segmentKey
);
127 segmentKey
= segment
->inE
->event
.tcpEvent
->segmentKey
;
129 convertIP(saddr
, segmentKey
->connectionKey
.saddr
);
130 convertIP(daddr
, segmentKey
->connectionKey
.daddr
);
131 g_debug("%s:%u to %s:%u tot_len: %u ihl: %u seq: %u ack_seq: %u doff: %u "
132 "ack: %u rst: %u syn: %u fin: %u", saddr
,
133 segmentKey
->connectionKey
.source
, daddr
, segmentKey
->connectionKey
.dest
,
134 segmentKey
->tot_len
, segmentKey
->ihl
, segmentKey
->seq
,
135 segmentKey
->ack_seq
, segmentKey
->doff
, segmentKey
->ack
, segmentKey
->rst
,
136 segmentKey
->syn
, segmentKey
->fin
);
141 * A GHashFunc for g_hash_table_new()
143 * This function is for indexing TCPEvents in unMatched lists. All fields of
144 * the corresponding SegmentKey must match for two keys to be equal.
150 * A hash of all fields in the SegmentKey
152 guint
ghfSegmentKeyHash(gconstpointer key
)
157 p
= (SegmentKey
*) key
;
159 a
= p
->connectionKey
.source
+ (p
->connectionKey
.dest
<< 16);
160 b
= p
->connectionKey
.saddr
;
161 c
= p
->connectionKey
.daddr
;
164 a
+= p
->ihl
+ (p
->tot_len
<< 8) + (p
->doff
<< 24);
169 a
+= p
->ack
+ (p
->rst
<< 8) + (p
->syn
<< 16) + (p
->fin
<< 24);
172 g_debug("segment key hash %p: %u", p
, c
);
179 * A GEqualFunc for g_hash_table_new()
181 * This function is for indexing TCPEvents in unMatched lists. All fields of
182 * the corresponding SegmentKey must match for two keys to be equal.
188 * TRUE if both values are equal
190 gboolean
gefSegmentKeyEqual(gconstpointer a
, gconstpointer b
)
192 const SegmentKey
* sA
, * sB
;
197 if (connectionKeyEqual(&sA
->connectionKey
, &sB
->connectionKey
) &&
198 sA
->ihl
== sB
->ihl
&&
199 sA
->tot_len
== sB
->tot_len
&&
200 sA
->seq
== sB
->seq
&&
201 sA
->ack_seq
== sB
->ack_seq
&&
202 sA
->doff
== sB
->doff
&&
203 sA
->ack
== sB
->ack
&&
204 sA
->rst
== sB
->rst
&&
205 sA
->syn
== sB
->syn
&&
208 g_debug("segment key equal %p %p: TRUE", sA
, sB
);
213 g_debug("segment key equal %p %p: FALSE", sA
, sB
);
220 * A GDestroyNotify function for g_hash_table_new_full()
225 void gdnDestroyEvent(gpointer data
)
229 event
->destroy(event
);
234 * A GDestroyNotify function for g_hash_table_new_full()
237 * data: GQueue* list[Packet]
239 void gdnTCPSegmentListDestroy(gpointer data
)
243 list
= (GQueue
*) data
;
245 g_queue_foreach(list
, &gfTCPSegmentDestroy
, NULL
);
251 * A GFunc for g_queue_foreach()
254 * data Message*, TCP message to destroy
257 void gfTCPSegmentDestroy(gpointer data
, gpointer user_data
)
259 destroyTCPSegment((Message
*) data
);
264 * Free the memory used by a TCP Message and the memory of all its associated
268 * segment TCP Message to destroy
270 void destroyTCPSegment(Message
* const segment
)
272 TCPEvent
* inE
, *outE
;
274 segment
->print(segment
);
276 g_assert(segment
->inE
!= NULL
&& segment
->outE
!= NULL
);
277 g_assert(segment
->inE
->type
== TCP
&& segment
->outE
->type
== TCP
);
278 inE
= segment
->inE
->event
.tcpEvent
;
279 outE
= segment
->outE
->event
.tcpEvent
;
280 g_assert(inE
->segmentKey
== outE
->segmentKey
);
282 outE
->segmentKey
= NULL
;
284 destroyTCPEvent(segment
->inE
);
285 destroyTCPEvent(segment
->outE
);
292 * Free the memory used by a TCP Exchange and the memory of SOME of its
293 * associated resources. The message is not destroyed. Use destroyTCPSegment()
297 * exchange TCP Exchange to destroy. The .message must be NULL
299 void destroyTCPExchange(Exchange
* const exchange
)
301 g_assert(exchange
->message
== NULL
);
303 if (exchange
->acks
!= NULL
)
305 g_queue_foreach(exchange
->acks
, &gfTCPSegmentDestroy
, NULL
);
306 g_queue_free(exchange
->acks
);
314 * Free the memory used by a TCP Event and its associated resources
316 void destroyTCPEvent(Event
* const event
)
318 g_assert(event
->type
== TCP
);
320 if (event
->event
.tcpEvent
->segmentKey
!= NULL
)
322 free(event
->event
.tcpEvent
->segmentKey
);
324 free(event
->event
.tcpEvent
);
325 event
->event
.tcpEvent
= NULL
;
331 * Free the memory used by a base Event
333 void destroyEvent(Event
* const event
)
335 g_assert(event
->event
.tcpEvent
== NULL
);
342 * Free the memory used by a UDP Event and its associated resources
344 void destroyUDPEvent(Event
* const event
)
346 g_assert(event
->type
== UDP
);
348 if (event
->event
.udpEvent
->datagramKey
!= NULL
)
350 free(event
->event
.udpEvent
->datagramKey
);
352 free(event
->event
.udpEvent
);
353 event
->event
.udpEvent
= NULL
;
359 * A GCompareFunc for g_queue_find_custom()
362 * a Message* acked packet
363 * b Message* ack packet
368 gint
gcfTCPSegmentAckCompare(gconstpointer a
, gconstpointer b
)
370 if (isAcking((const Message
*) b
, (const Message
*) a
))
382 * A GHashFunc for g_hash_table_new()
384 * Hash TCP connection keys. Here are a few possible implementations:
386 * 2.4 kernels used tcp_hashfn()
388 * I've seen something about an XOR hash:
389 * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14:
390 * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
395 * In 2.6 kernels, inet_ehashfn() handles connection hashing with the help of
396 * Jenkins hashing, jhash.h
398 * This function uses jenkins hashing. The hash is not the same for packets in
399 * opposite directions of the same connection. (Hence the name
400 * connection*key*hash)
405 guint
ghfConnectionKeyHash(gconstpointer key
)
407 ConnectionKey
* connectionKey
;
410 connectionKey
= (ConnectionKey
*) key
;
412 a
= connectionKey
->source
+ (connectionKey
->dest
<< 16);
413 b
= connectionKey
->saddr
;
414 c
= connectionKey
->daddr
;
422 * A GEqualFunc for g_hash_table_new()
425 * a, b ConnectionKey*
428 * TRUE if both values are equal
430 gboolean
gefConnectionKeyEqual(gconstpointer a
, gconstpointer b
)
432 // Two packets in the same direction
433 if (connectionKeyEqual((const ConnectionKey
*) a
, (const ConnectionKey
*) b
))
445 * A GDestroyNotify function for g_hash_table_new_full()
448 * data: ConnectionKey*
450 void gdnConnectionKeyDestroy(gpointer data
)
452 free((ConnectionKey
*) data
);
457 * A GHashFunc for g_hash_table_new()
462 guint
ghfDatagramKeyHash(gconstpointer key
)
464 DatagramKey
* datagramKey
;
467 uint32_t hashableKey
[2];
471 datagramKey
= (DatagramKey
*) key
;
472 memcpy(dataKey
.byteKey
, datagramKey
->dataKey
, sizeof(dataKey
.byteKey
));
474 a
= datagramKey
->saddr
;
475 b
= datagramKey
->daddr
;
476 c
= datagramKey
->source
+ (datagramKey
->dest
<< 16);
479 a
+= datagramKey
->ulen
; // 16 bits left here
480 b
+= dataKey
.hashableKey
[0];
481 c
+= dataKey
.hashableKey
[1];
489 * A GEqualFunc for g_hash_table_new()
495 * TRUE if both values are equal
497 gboolean
gefDatagramKeyEqual(gconstpointer a
, gconstpointer b
)
499 const DatagramKey
* dA
, * dB
;
501 dA
= (DatagramKey
*) a
;
502 dB
= (DatagramKey
*) b
;
504 if (dA
->saddr
== dB
->saddr
&& dA
->daddr
== dB
->daddr
&&
505 dA
->source
== dB
->source
&& dA
->dest
== dB
->dest
&&
506 dA
->ulen
== dB
->ulen
&&
507 memcmp(dA
->dataKey
, dB
->dataKey
, sizeof(dA
->dataKey
)) == 0)
519 * A GDestroyNotify function for g_hash_table_new_full()
524 void gdnDestroyDatagramKey(gpointer data
)
526 free((DatagramKey
*) data
);
531 * A GDestroyNotify function for g_hash_table_new_full()
536 void gdnDestroyBroadcast(gpointer data
)
538 destroyBroadcast((Broadcast
*) data
);
543 * Free a Broadcast struct and its associated ressources
546 * broadcast: Broadcast*
548 void destroyBroadcast(Broadcast
* const broadcast
)
550 g_queue_foreach(broadcast
->events
, &gfDestroyEvent
, NULL
);
551 g_queue_free(broadcast
->events
);
557 * A GFunc for g_queue_foreach()
563 void gfDestroyEvent(gpointer data
, gpointer user_data
)
567 event
->destroy(event
);
571 /* Subtract two WallTime structs
577 * The result of tA - tB, as a double. This may incur a loss of
580 double wallTimeSub(const WallTime
const* tA
, const WallTime
const* tB
)
582 return (double) tA
->seconds
- tB
->seconds
+ ((double) tA
->nanosec
- tB
->nanosec
) / 1e9
;
587 * Allocate and copy a base event
590 * newEvent: new event, pointer will be updated
591 * event: event to copy
593 void copyEvent(const Event
* const event
, Event
** const newEvent
)
595 g_assert(event
->event
.tcpEvent
== NULL
);
597 *newEvent
= malloc(sizeof(Event
));
598 memcpy(*newEvent
, event
, sizeof(Event
));
603 * Allocate and copy a TCP event
606 * newEvent: new event, pointer will be updated
607 * event: event to copy
609 void copyTCPEvent(const Event
* const event
, Event
** const newEvent
)
611 g_assert(event
->type
== TCP
);
613 *newEvent
= malloc(sizeof(Event
));
614 memcpy(*newEvent
, event
, sizeof(Event
));
616 (*newEvent
)->event
.tcpEvent
= malloc(sizeof(TCPEvent
));
617 memcpy((*newEvent
)->event
.tcpEvent
, event
->event
.tcpEvent
,
620 (*newEvent
)->event
.tcpEvent
->segmentKey
= malloc(sizeof(SegmentKey
));
621 memcpy((*newEvent
)->event
.tcpEvent
->segmentKey
,
622 event
->event
.tcpEvent
->segmentKey
, sizeof(SegmentKey
));
627 * Allocate and copy a UDP event
630 * newEvent: new event, pointer will be updated
631 * event: event to copy
633 void copyUDPEvent(const Event
* const event
, Event
** const newEvent
)
635 g_assert(event
->type
== UDP
);
637 *newEvent
= malloc(sizeof(Event
));
638 memcpy(*newEvent
, event
, sizeof(Event
));
640 (*newEvent
)->event
.udpEvent
= malloc(sizeof(UDPEvent
));
641 memcpy((*newEvent
)->event
.udpEvent
, event
->event
.udpEvent
,
644 (*newEvent
)->event
.udpEvent
->datagramKey
= malloc(sizeof(DatagramKey
));
645 memcpy((*newEvent
)->event
.udpEvent
->datagramKey
,
646 event
->event
.udpEvent
->datagramKey
, sizeof(DatagramKey
));
651 * A GFunc for g_queue_foreach()
654 * data Event*, event to add
655 * user_data GArray*, array to add to
657 void gfAddEventToArray(gpointer data
, gpointer user_data
)
659 g_array_append_val((GArray
*) user_data
, data
);
667 * factorsCHull: container of Factors
669 void destroyPairFactors(PairFactors
* pairFactors
)
671 if (pairFactors
->min
!= NULL
)
673 free(pairFactors
->min
);
675 if (pairFactors
->max
!= NULL
)
677 free(pairFactors
->max
);
679 if (pairFactors
->approx
!= NULL
)
681 free(pairFactors
->approx
);
687 * Create and initialize a container of PairFactors
690 * traceNb: number of traces
693 * A new array, which can be freed with freeAllFactors()
695 AllFactors
* createAllFactors(const unsigned int traceNb
)
697 AllFactors
* allFactors
;
698 PairFactors
** factorsArray
;
701 allFactors
= malloc(sizeof(AllFactors
));
702 allFactors
->refCount
= 1;
703 allFactors
->pairFactors
= malloc(traceNb
* sizeof(PairFactors
*));
704 factorsArray
=allFactors
->pairFactors
;
705 for (i
= 0; i
< traceNb
; i
++)
707 factorsArray
[i
]= calloc(traceNb
, sizeof(PairFactors
));
709 for (j
= 0; j
< traceNb
; j
++)
713 factorsArray
[i
][i
].type
= EXACT
;
714 factorsArray
[i
][i
].approx
= malloc(sizeof(Factors
));
715 factorsArray
[i
][i
].approx
->drift
= 1.;
716 factorsArray
[i
][i
].approx
->offset
= 0.;
720 factorsArray
[i
][j
].type
= ABSENT
;
730 * Free a container of PairFactors
733 * allFactors: container of PairFactors
734 * traceNb: number of traces
736 void freeAllFactors(AllFactors
* const allFactors
, const unsigned int traceNb
)
740 if (allFactors
== NULL
)
745 allFactors
->refCount
--;
747 if (allFactors
->refCount
== 0)
749 for (i
= 0; i
< traceNb
; i
++)
751 for (j
= 0; j
< traceNb
; j
++)
753 destroyPairFactors(&allFactors
->pairFactors
[i
][j
]);
755 free(allFactors
->pairFactors
[i
]);
757 free(allFactors
->pairFactors
);
This page took 0.055984 seconds and 4 git commands to generate.