ceph/src/seastar/include/seastar/net/packet-util.hh

   1 /*
   2  * This file is open source software, licensed to you under the terms
   3  * of the Apache License, Version 2.0 (the "License").  See the NOTICE file
   4  * distributed with this work for additional information regarding copyright
   5  * ownership.  You may not use this file except in compliance with the License.
   6  *
   7  * You may obtain a copy of the License at
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing,
  12  * software distributed under the License is distributed on an
  13  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14  * KIND, either express or implied.  See the License for the
  15  * specific language governing permissions and limitations
  16  * under the License.
  17  */
  18 /*
  19  * Copyright (C) 2014 Cloudius Systems, Ltd.
  20  */
  21
  22 #pragma once
  23
  24 #include <seastar/net/packet.hh>
  25 #include <map>
  26 #include <iostream>
  27
  28 namespace seastar {
  29
  30 namespace net {
  31
  32 template <typename Offset, typename Tag>
  33 class packet_merger {
  34 private:
  35     static uint64_t& linearizations_ref() {
  36         static thread_local uint64_t linearization_count;
  37         return linearization_count;
  38     }
  39 public:
  40     std::map<Offset, packet> map;
  41
  42     static uint64_t linearizations() {
  43         return linearizations_ref();
  44     }
  45
  46     void merge(Offset offset, packet p) {
  47         bool insert = true;
  48         auto beg = offset;
  49         auto end = beg + p.len();
  50         // Fisrt, try to merge the packet with existing segment
  51         for (auto it = map.begin(); it != map.end();) {
  52             auto& seg_pkt = it->second;
  53             auto seg_beg = it->first;
  54             auto seg_end = seg_beg + seg_pkt.len();
  55             // There are 6 cases:
  56             if (seg_beg <= beg && end <= seg_end) {
  57                 // 1) seg_beg beg end seg_end
  58                 // We already have data in this packet
  59                 return;
  60             } else if (beg <= seg_beg && seg_end <= end) {
  61                 // 2) beg seg_beg seg_end end
  62                 // The new segment contains more data than this old segment
  63                 // Delete the old one, insert the new one
  64                 it = map.erase(it);
  65                 insert = true;
  66                 break;
  67             } else if (beg < seg_beg && seg_beg <= end && end <= seg_end) {
  68                 // 3) beg seg_beg end seg_end
  69                 // Merge two segments, trim front of old segment
  70                 auto trim = end - seg_beg;
  71                 seg_pkt.trim_front(trim);
  72                 p.append(std::move(seg_pkt));
  73                 // Delete the old one, insert the new one
  74                 it = map.erase(it);
  75                 insert = true;
  76                 break;
  77             } else if (seg_beg <= beg && beg <= seg_end && seg_end < end) {
  78                 // 4) seg_beg beg seg_end end
  79                 // Merge two segments, trim front of new segment
  80                 auto trim = seg_end - beg;
  81                 p.trim_front(trim);
  82                 // Append new data to the old segment, keep the old segment
  83                 seg_pkt.append(std::move(p));
  84                 seg_pkt.linearize();
  85                 ++linearizations_ref();
  86                 insert = false;
  87                 break;
  88             } else {
  89                 // 5) beg end < seg_beg seg_end
  90                 //   or
  91                 // 6) seg_beg seg_end < beg end
  92                 // Can not merge with this segment, keep looking
  93                 it++;
  94                 insert = true;
  95             }
  96         }
  97
  98         if (insert) {
  99             p.linearize();
 100             ++linearizations_ref();
 101             map.emplace(beg, std::move(p));
 102         }
 103
 104         // Second, merge adjacent segments after this packet has been merged,
 105         // becasue this packet might fill a "whole" and make two adjacent
 106         // segments mergable
 107         for (auto it = map.begin(); it != map.end();) {
 108             // The first segment
 109             auto& seg_pkt = it->second;
 110             auto seg_beg = it->first;
 111             auto seg_end = seg_beg + seg_pkt.len();
 112
 113             // The second segment
 114             auto it_next = it;
 115             it_next++;
 116             if (it_next == map.end()) {
 117                 break;
 118             }
 119             auto& p = it_next->second;
 120             auto beg = it_next->first;
 121             auto end = beg + p.len();
 122
 123             // Merge the the second segment into first segment if possible
 124             if (seg_beg <= beg && beg <= seg_end && seg_end < end) {
 125                 // Merge two segments, trim front of second segment
 126                 auto trim = seg_end - beg;
 127                 p.trim_front(trim);
 128                 // Append new data to the first segment, keep the first segment
 129                 seg_pkt.append(std::move(p));
 130
 131                 // Delete the second segment
 132                 map.erase(it_next);
 133
 134                 // Keep merging this first segment with its new next packet
 135                 // So we do not update the iterator: it
 136                 continue;
 137             } else if (end <= seg_end) {
 138                 // The first segment has all the data in the second segment
 139                 // Delete the second segment
 140                 map.erase(it_next);
 141                 continue;
 142             } else if (seg_end < beg) {
 143                 // Can not merge first segment with second segment
 144                 it = it_next;
 145                 continue;
 146             } else {
 147                 // If we reach here, we have a bug with merge.
 148                 std::cout << "packet_merger: merge error\n";
 149                 abort();
 150                 break;
 151             }
 152         }
 153     }
 154 };
 155
 156 }
 157
 158 }