ceph/src/msg/async/dpdk/PacketUtil.h

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