in reply to Re: Sorting out troubles with advanced-ish sort
in thread Sorting out troubles with advanced-ish sort

Ok, so it looks like your nudge nudged me enough. The loop now looks like this:

for my $line( map { $_->[2] } sort { $a->[0] cmp $b->[0] || $a->[1] <=> $b->[1] } map { my @vals = split /\s/, $_; my( $sourceserv, $sourceport ) = (split /:/, $vals +[0])[0,1]; my( $destserv, $destport ) = (split /:/, $vals[2] +)[0,1]; my( $low, $high ) = sort { $a cmp $b } ( "$sourceserv:$sourceport", "$destserv:$destpor +t" ); my( $key ) = $low . '-' . $high; [ $key, $sourceport , $_ ] } <DATA> ){ print $line; }

And the output as desired:

10.10.10.5:1000 -> 10.10.10.10:8000 10.10.10.5:1000 -> 10.10.10.10:8000 10.10.10.10:8000 -> 10.10.10.5:1000 10.10.10.10:8000 -> 10.10.10.5:1000 10.10.10.10:8000 -> 10.10.10.5:1000 10.10.10.5:1001 -> 10.10.10.10:8000 10.10.10.5:1001 -> 10.10.10.10:8000 10.10.10.10:8000 -> 10.10.10.5:1001 10.10.10.6:1000 -> 10.10.10.10:8000 10.10.10.6:1000 -> 10.10.10.10:8000 10.10.10.10:8000 -> 10.10.10.6:1000 10.10.10.6:1001 -> 10.10.10.10:8000 10.10.10.6:1001 -> 10.10.10.10:8000 10.10.10.10:8000 -> 10.10.10.6:1001 10.10.10.7:1000 -> 10.10.10.10:8000

Is this efficient? I don't know. Will it run "fast enough"? Also don't know. But I suppose I could let it chug along while I'm here on a Saturday, and if it's still running after I leave, so be it :) (Please don't ask how large the capture file is ;)

Thanks much!



--chargrill
$,=42;for(34,0,-3,9,-11,11,-17,7,-5){$*.=pack'c'=>$,+=$_}for(reverse s +plit//=>$* ){$%++?$ %%2?push@C,$_,$":push@c,$_,$":(push@C,$_,$")&&push@c,$"}$C[$# +C]=$/;($#C >$#c)?($ c=\@C)&&($ C=\@c):($ c=\@c)&&($C=\@C);$%=$|;for(@$c){print$_^ +$$C[$%++]}

Replies are listed 'Best First'.
Re^3: Sorting out troubles with advanced-ish sort
by japhy (Canon) on May 06, 2006 at 18:02 UTC
    I'd recommend cleaning the map up a bit:
    map { my ($src, $dst) = (split)[0,2]; my ($src_port) = $src =~ /:(\d+)/; ($src, $dst) = ($dst, $src) if $dst lt $src; [ "$src-$dst", $src_port, $_ ] }
    It just looks tidier to me. By the way, what about when you get an address like 10.10.10.14 as the source? That'll sort before 10.10.10.5, so perhaps you should convert the IPs into 4-byte sequences.

    Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
    How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
      By the way, what about when you get an address like 10.10.10.14 as the source? That'll sort before 10.10.10.5, so perhaps you should convert the IPs into 4-byte sequences.

      When packed, the strings will be shorter and we could use the default { $a cmp $b } compare function. That makes the packed version much faster, and it would require less memory. Note the ingenious use of 0 or 1 to in lieu of $src.

      print map { substr($_, 13) } sort map { my ($src, $dst) = (split)[0, 2]; $src = pack('C4n', split(/[.:]/, $src)); $dst = pack('C4n', split(/[.:]/, $dst)); $src lt $dst ? "$src${dst}0$_" : "$dst${src}1$_" } <DATA>;

      Actually, adding $_ is redundant, since we can reconstruct it. The following would cut the memory usage in half:

      print map { my @f = unpack('C4nC4na', $_); my $src = "$f[0].$f[1].$f[2].$f[3]:$f[4]"; my $dst = "$f[5].$f[6].$f[7].$f[8]:$f[9]"; ($src, $dst) = ($dst, $src) if $f[10]; "$src -> $dst\n" } sort map { my ($src, $dst) = (split)[0, 2]; $src = pack('C4n', split(/[.:]/, $src)); $dst = pack('C4n', split(/[.:]/, $dst)); $src lt $dst ? "$src${dst}0" : "$dst${src}1" } <DATA>;

      Both of the above have been tested. They only work if the addresses are IPv4 addresses in dotted form.

      By the way, if you have memory problems, you could use an external sort tool as follows:

      { open(local *TEMP, '>', $sort_input); while (<DATA>) { my ($src, $dst) = (split)[0, 2]; $src = pack('C4n', split(/[.:]/, $src)); $dst = pack('C4n', split(/[.:]/, $dst)); my $data = $src lt $dst ? "$src${dst}0" : "$dst${src}1"; print TEMP (unpack('H*', $data), "\n"); } } ...[ call external sort tool ]... { open(local *TEMP, '<', $sort_output); while (<TEMP>) { chomp; my @f = unpack('C4nC4na', pack('H*', $_)); my $src = "$f[0].$f[1].$f[2].$f[3]:$f[4]"; my $dst = "$f[5].$f[6].$f[7].$f[8]:$f[9]"; ($src, $dst) = ($dst, $src) if $f[10]; print("$src -> $dst\n"); } }

      The convertion to hex is to avoid having newlines in your data.

        All very good suggestions, but I will add the following points:

        1. I don't much care the particular order of the IP conversations - 10.10.10.5, 10.10.10.50, 10.10.10.14 can come in any order, so long as each combination of source and port are together, and the 'bar' server replies follow the 'foo' server requests.
        2. If only the data I needed was what I wrote in my example - I have the rest of the packet information that I care about - I'm specifically looking for conversations from server 'foo' that don't end with a FIN (an issue known to cause server 'bar' issues (the 'bar' server blocks on trying to read the port) so that no other server 'foo' can be serviced by the single server 'bar'). As such, my data structure (after passing through the file once) roughly looks like this:
          # $type consisting of one of ( fin, syn, rst, ack ) #my @packetlog = ( # { # '$source:$port' => [ $type, $seq, $length ], # 'packet' => [ $frame, $src, $dest, $deltaT, $abs, $rel, $cumu +, $byt ], # } # );
          Therefore, the (working version of the) last map is quite a bit different than my simplified (working version for my) example:
          map { my( $v, $k ) = keys %$_; my $val = $v =~ /pack/ ? $k : $v; my( $src, $srcP, $dst, $dstP ) = split /:/, $val; my( $low, $high ) = sort { $a cmp $b } ( "$src:$srcP", "$dst:$ds +tP" ); my $key = $high . '-' . $low; [ $key, $srcP, $_ ] }
          And I can certainly clean things up to more closely match the suggestions by ikegami and japhy, but it's not (for me, anyhow) a simple conversion :)
        3. Thankfully, the above suits my purposes, as the code was able to identify my test case (in this instance, someone telneted to the 'bar' server's service port and didn't send anything which triggered the 'bar' server to block on that port and stop servicing requests from any other server).
        4. Packing the IPs according to ikegami's post will probably eliminate some cycles, but I don't think I can eliminate $_ from the anonymous array at the end of the map, because it contains a lot more information :)
        5. As written above, it processes roughly 371,000 lines in about 76 seconds on my box. This includes the initial parsing of the file to create the above structure.
        6. Also, i don't *really* want to print all ~371,000 lines, but I would like to capture anything matching my criteria. From suggestions from ikegami and johngg, moving the print outside the loop (therefore dispensing with the for) seems to make sense, but since I don't know I've found an offender until the end of the conversation, my real code keeps track of the last N packets, discarding them if they don't appear to end in an anomalous manner.


          --chargrill
          $,=42;for(34,0,-3,9,-11,11,-17,7,-5){$*.=pack'c'=>$,+=$_}for(reverse s +plit//=>$* ){$%++?$ %%2?push@C,$_,$":push@c,$_,$":(push@C,$_,$")&&push@c,$"}$C[$# +C]=$/;($#C >$#c)?($ c=\@C)&&($ C=\@c):($ c=\@c)&&($C=\@C);$%=$|;for(@$c){print$_^ +$$C[$%++]}
Re^3: Sorting out troubles with advanced-ish sort
by johngg (Canon) on May 06, 2006 at 20:20 UTC
    Since print operates on a list you could dispense with the

    for my $line ( map { ... } sort { ... } map { ... } <DATA>) { print $line; }

    and just do

    print map { ... } sort { ... } map { ... } <DATA>;

    without the need to assign each line before printing it. It looks a little easier to my eye.

    Cheers,

    JohnGG