RangeList.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#ifndef KERNEL_UTILITIES_RANGELIST_H
#define KERNEL_UTILITIES_RANGELIST_H
 
#include "pedigree/kernel/compiler.h"
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/StaticString.h"
#include "pedigree/kernel/utilities/Vector.h"
 
template <typename T, bool Reversed = false>
class EXPORTED_PUBLIC RangeList {
 public:
  inline RangeList() : m_List(), m_bPreferUsed(false) {}
  inline RangeList(bool preferUsed) : m_List(), m_bPreferUsed(preferUsed) {}
  RangeList(T Address, T Length, bool XXX, bool preferUsed = false)
      : m_List(), m_bPreferUsed(preferUsed) {
    m_List.pushBack(Range(Address, Length));
  }
  ~RangeList();
 
  RangeList(const RangeList&);
  RangeList& operator=(const RangeList& l);
 
  struct Range {
    Range() = default;
    Range(T Address, T Length) : address(Address), length(Length) {}
 
    T address;
    T length;
 
    bool operator==(const Range& other) const {
      return (address == other.address) && (length == other.length);
    }
  };
 
  void free(T address, T length, bool merge = true);
  bool tryFree(T address, T length, bool merge = true);
  bool freeWithoutAllocation(T address, T length);
  bool allocateWithoutAllocation(T length, T& address);
  bool allocateSpecificWithoutAllocation(T address, T length);
 
  bool allocate(T length, T& address);
  bool allocateSpecific(T address, T length);
  void clear();
  void swap(RangeList& other) noexcept {
    m_List.swap(other.m_List);
    const bool preferUsed = m_bPreferUsed;
    m_bPreferUsed = other.m_bPreferUsed;
    other.m_bPreferUsed = preferUsed;
  }
 
  inline size_t size() const {
    return m_List.count();
  }
  bool getRange(size_t index, Range& range) const;
 
  void sweep();
 
  void dump(void (*emit_line)(const char* s)) const;
 
 private:
  Vector<Range> m_List;
 
  bool m_bPreferUsed;
 
  typedef typename decltype(m_List)::Iterator Iterator;
  typedef typename decltype(m_List)::ConstIterator ConstIterator;
  typedef typename decltype(m_List)::ReverseIterator ReverseIterator;
  typedef typename decltype(m_List)::ConstReverseIterator ConstReverseIterator;
};
 
template <typename T, bool Reversed>
RangeList<T, Reversed>::RangeList(const RangeList<T, Reversed>& other)
    : m_List(), m_bPreferUsed(other.m_bPreferUsed) {
  for (ConstIterator it = other.m_List.begin(); it != other.m_List.end(); ++it) {
    m_List.pushBack(*it);
  }
}
 
template <typename T, bool Reversed>
RangeList<T, Reversed>& RangeList<T, Reversed>::operator=(const RangeList& other) {
  if (this == &other) {
    return *this;
  }
  // Need to clean up all our existing ranges.
  clear();
  m_bPreferUsed = other.m_bPreferUsed;
 
  for (ConstIterator it = other.m_List.begin(); it != other.m_List.end(); ++it) {
    m_List.pushBack(*it);
  }
 
  return *this;
}
 
template <typename T, bool Reversed>
void RangeList<T, Reversed>::free(T address, T length, bool merge) {
  if (merge) {
    Iterator cur = m_List.begin();
    ConstIterator end = m_List.end();
 
    // Try and find a place to merge immediately.
    bool needsNew = true;
    for (; cur != end; ++cur) {
      // Region ends at our freed address.
      if ((cur->address + cur->length) == address) {
        // Update - all done.
        cur->length += length;
        needsNew = false;
        break;
      }
      // Region starts after our address.
      else if (cur->address == (address + length)) {
        // Expand.
        cur->address -= length;
        cur->length += length;
        needsNew = false;
        break;
      }
    }
 
    if (!needsNew)
      return;
  }
 
  // Couldn't find a merge or didn't want one, so we need to add a new region.
 
  // Add the range back to our list, but in such a way that it is allocated
  // last rather than first (if another allocation of the same length comes
  // later).
  Range range(address, length);
 
  // Decide which side of the list to push to. If we prefer used ranges over
  // fresh ranges, we want to invert the push decision.
  bool front = Reversed;
  if (m_bPreferUsed)
    front = !front;
 
  if (front)
    m_List.pushFront(range);
  else
    m_List.pushBack(range);
 
  // NOTE: we defer sweeping to allocate(), and only if a first attempt at
  // allocate() fails to successfully find a range it can use. This saves
  // time when freeing regions and is useful for RangeLists that are not
  // heavily utilized.
}
 
template <typename T, bool Reversed>
bool RangeList<T, Reversed>::tryFree(T address, T length, bool merge) {
  if (merge && freeWithoutAllocation(address, length)) {
    return true;
  }
  if (!m_List.tryReserve(m_List.count() + 1)) {
    return false;
  }
  Range range(address, length);
  if (Reversed != m_bPreferUsed) {
    m_List.pushFront(range);
  } else {
    m_List.pushBack(range);
  }
  return true;
}
 
template <typename T, bool Reversed>
bool RangeList<T, Reversed>::freeWithoutAllocation(T address, T length) {
  if (!length) {
    return true;
  }
  size_t empty = m_List.count();
  for (size_t i = 0; i < m_List.count(); ++i) {
    Range* range = &m_List[i];
    if (!range->length) {
      empty = i;
    } else if (range->address + range->length == address) {
      range->length += length;
      return true;
    } else if (range->address == address + length) {
      range->address = address;
      range->length += length;
      return true;
    }
  }
  if (empty == m_List.count()) {
    return false;
  }
  m_List.erase(empty);
  Range range(address, length);
  if (Reversed != m_bPreferUsed) {
    m_List.pushFront(range);
  } else {
    m_List.pushBack(range);
  }
  return true;
}
 
template <typename T, bool Reversed>
bool RangeList<T, Reversed>::allocateWithoutAllocation(T length, T& address) {
  if (!length) {
    return false;
  }
  for (size_t i = 0; i < m_List.count(); ++i) {
    Range* range = &m_List[Reversed ? m_List.count() - 1 - i : i];
    if (range->length < length) {
      continue;
    }
    address = Reversed ? range->address + range->length - length : range->address;
    if (!Reversed) {
      range->address += length;
    }
    range->length -= length;
    return true;
  }
  return false;
}
 
template <typename T, bool Reversed>
bool RangeList<T, Reversed>::allocateSpecificWithoutAllocation(T address, T length) {
  if (!length) {
    return false;
  }
  for (size_t i = 0; i < m_List.count(); ++i) {
    Range* range = &m_List[i];
    if (address < range->address || address - range->address > range->length ||
        length > range->length - (address - range->address)) {
      continue;
    }
    const T prefix = address - range->address;
    const T suffix = range->length - prefix - length;
    if (prefix && suffix) {
      Range* spare = nullptr;
      for (size_t j = 0; j < m_List.count(); ++j) {
        if (!m_List[j].length) {
          spare = &m_List[j];
          break;
        }
      }
      if (!spare) {
        return false;
      }
      spare->address = address + length;
      spare->length = suffix;
      range->length = prefix;
    } else if (prefix) {
      range->length = prefix;
    } else {
      range->address += length;
      range->length = suffix;
    }
    return true;
  }
  return false;
}
 
template <typename T, bool Reversed>
bool RangeList<T, Reversed>::allocate(T length, T& address) {
  bool bSuccess = false;
 
  for (int i = 0; i < 2; ++i) {
    for (size_t j = 0; j < m_List.count(); ++j) {
      const size_t index = Reversed ? m_List.count() - 1 - j : j;
      Range& range = m_List[index];
      if (range.length < length) {
        continue;
      }
 
      if (Reversed) {
        // Big enough. Cut into the END of this range.
        T offset = range.length - length;
        address = range.address + offset;
      } else {
        address = range.address;
        range.address += length;
      }
      range.length -= length;
 
      // Remove if the entry no longer exists.
      if (!range.length) {
        m_List.erase(index);
      }
 
      bSuccess = true;
      break;
    }
 
    if (bSuccess) {
      return true;
    } else if (!i) {
      // Failed on first pass, try another pass after a sweep.
      // The sweep could merge some regions and let us allocate.
      // This is better than sweeping on every single allocation, which
      // could be really slow and unnecessary.
      sweep();
    }
  }
 
  return bSuccess;
}
 
template <typename T, bool Reversed>
bool RangeList<T, Reversed>::allocateSpecific(T address, T length) {
  bool bSuccess = false;
  for (int i = 0; i < 2; ++i) {
    for (size_t j = 0; j < m_List.count(); ++j) {
      Range* cur = &m_List[j];
      // Precise match.
      if (cur->address == address && cur->length == length) {
        m_List.erase(j);
        bSuccess = true;
        break;
      }
 
      // Match at end.
      else if (address > cur->address && (cur->address + cur->length) == (address + length)) {
        cur->length -= length;
        bSuccess = true;
        break;
      }
 
      // Match at start.
      else if (cur->address == address && cur->length > length) {
        cur->address += length;
        cur->length -= length;
        bSuccess = true;
        break;
      }
 
      // Match within.
      else if (address > cur->address && (cur->address + cur->length) > (address + length)) {
        // Need to split the range.
        const T suffix = cur->address + cur->length - address - length;
        const T prefix = address - cur->address;
        if (!m_List.tryReserve(m_List.count() + 1)) {
          return false;
        }
        // Growing the value buffer can move the original range.
        m_List[j].length = prefix;
        m_List.pushBack(Range(address + length, suffix));
        bSuccess = true;
        break;
      }
    }
 
    if (bSuccess) {
      return bSuccess;
    } else if (!i) {
      // Failed in the first pass, sweep to merge potential regions and
      // then we'll try again.
      sweep();
    }
  }
 
  return bSuccess;
}
 
template <typename T, bool Reversed>
bool RangeList<T, Reversed>::getRange(size_t index, Range& range) const {
  range = Range(0, 0);
  if (index >= m_List.count())
    return false;
 
  range = m_List[index];
  return true;
}
 
template <typename T, bool Reversed>
RangeList<T, Reversed>::~RangeList() {
  clear();
}
 
template <typename T, bool Reversed>
void RangeList<T, Reversed>::clear() {
  m_List.clear();
}
 
template <typename T, bool Reversed>
void RangeList<T, Reversed>::sweep() {
  if (m_List.count() < 2) {
    return;
  }
 
  // Storage order preserves allocation preferences; adjacent addresses need
  // not be neighboring entries. Keep the first entry's position when merging.
  for (size_t i = 0; i < m_List.count(); ++i) {
    for (size_t j = i + 1; j < m_List.count();) {
      Range* cur = &m_List[i];
      Range* next = &m_List[j];
      if (cur->address + cur->length == next->address) {
        cur->length += next->length;
      } else if (next->address + next->length == cur->address) {
        cur->address = next->address;
        cur->length += next->length;
      } else {
        ++j;
        continue;
      }
      m_List.erase(j);
      // The enlarged range can now reach an entry we passed earlier.
      j = i + 1;
    }
  }
}
 
template <typename T, bool Reversed>
void RangeList<T, Reversed>::dump(void (*emit_line)(const char* s)) const {
  for (size_t i = 0; i < m_List.count(); ++i) {
    const Range* range = &m_List[i];
 
    HugeStaticString str;
    str.append("range ");
    str.append(range->address, 16, 16, '0');
    str.append(" -> ");
    str.append(range->address + range->length, 16, 16, '0');
    str.append(" (");
    str.append(range->length, 10);
    str.append(" bytes)");
    emit_line(static_cast<const char*>(str));
  }
}
 
extern template class RangeList<uint64_t>;  // IWYU pragma: keep
extern template class RangeList<uint32_t>;  // IWYU pragma: keep
 
#endif