memory.cc

#ifndef _GNU_SOURCE
  #define _GNU_SOURCE
#endif

#include <algorithm>
#include <iostream>
#include <ctime>
#include <cerrno>
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <fcntl.h>
#include <stdlib.h>
#include <sched.h>
#include <unistd.h>
#include <math.h>
#include <climits>
#include <signal.h>
#include <vector>
#include <list>
#include <sys/mman.h>
#include <sys/sysinfo.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <sys/ioctl.h>
#include <sys/prctl.h>
#include <asm/unistd.h>

#include "memory.h"
#include "utils.h"


// if a memory area is contiguous the distances between the rows follow
// one of those four patterns. They are calculated from the reverse engineered
// DRAM mapping (see get_addressing_bits, bit 8 is ignored)
int contiguous_memory_distance_pattern[][16] = {
  {8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 1},
  {8, 7, 8, 11, 8, 7, 8, 11, 8, 7, 8, 11, 8, 7, 8, 3},
  {8, 9, 8, 5, 8, 9, 8, 13, 8, 9, 8, 5, 8, 9, 8, 5},
  {8, 7, 8, 7, 8, 7, 8, 15, 8, 7, 8, 7, 8, 7, 8, 7},
};

#if FIND_ROWS_METHOD == FIND_ROWS_METHOD_MAPPING
int find_rows_hugepage(volatile uint8_t *mem, size_t len, std::vector<uint8_t*> &rows, int start) {
  volatile uint8_t *aggr[2];
  int found_rows = 1;
  int rowIdx;
  uintptr_t addr = (uintptr_t) mem + (start << 12);

  rows.resize(64);

  rowIdx = get_row_number(addr);
  rows[rowIdx] = (uint8_t*) addr;

  for (int i = rowIdx - 1; i >= 0; i--) {
    rows[i] = (uint8_t*) get_prev_row((uintptr_t) rows[i + 1]);
  }

  for (int i = rowIdx + 1; i < 64; i++) {
    rows[i] = (uint8_t*) get_next_row((uintptr_t) rows[i - 1]);
  }

  return 64;
}
#elif FIND_ROWS_METHOD == FIND_ROWS_METHOD_TIMING
// using the timing difference between a same-bank row access and
// different-bank row access to find rows in the same bank
// and fill rows with pointers the rows
int find_rows_hugepage(volatile uint8_t *mem, size_t len, std::vector<uint8_t*> &rows, int start) {
  volatile uint8_t *aggr[2];
  int found_rows = 1;
  int rowIdx;

  rows.resize(64);

  aggr[0] = mem + (start << 12);
  rowIdx = get_row_number((uintptr_t) aggr[0]);
  rows[rowIdx] = (uint8_t*) aggr[0];

  for (size_t i = 0; i < len; i += 0x1000) {
    aggr[1] = mem + i;

    uint64_t start = ns();

    for (int j = 0; j < 250000; j++) {
      *(aggr[0]);
      *(aggr[1]);
      isb();
      #ifdef FLUSH
      flush((void*) aggr[0]);
      flush((void*) aggr[1]);
      #endif
    }

    uint64_t duration = ns() - start;

#ifdef FLUSH
    if (duration / 1000 > 52000) {  //56000
#else
    if (duration / 1000 > 23000) {
#endif
      rowIdx = get_row_number((uintptr_t) aggr[1]);

      if (rowIdx > 63) {
        printf(COLOR_RED "row index > 63, aborting\n" COLOR_RESET);
        return 0;
      }

      printf("\r%lx\t%ld\t%d\t%p\t0x%lx\t", i, duration / 1000, 
             rowIdx, aggr[1],
             get_ppn((uintptr_t) aggr[1]) * 0x1000);
      print_addressing_bits((uintptr_t) aggr[1]);
      printf("\n");
      fflush(stdout);

      rows[rowIdx] = (uint8_t*) aggr[1];
      found_rows++;
    }
#ifndef FLUSH
    else if (duration / 1000 < 3500) {
      return 0;
    }
#endif
  }

  printf("found %d rows\n", found_rows);

  if (found_rows != 1)
    printf("\n");
  
  return found_rows;
}
#endif

int find_rows_no_hugepage(volatile uint8_t *mem, size_t len, std::vector<uint8_t*> &rows, int start) {
  volatile uint8_t *aggr[2];
  int found_rows = 1;
  int prev_index = 0;

  size_t idx = 0;
  size_t bank_idx = 0;
  bool contiguous = false;
  size_t contiguous_start_idx = 0;
  std::list<int> distance_history;
  std::vector<int> chunks;

  int64_t prev_paddr = 0;

  rows.clear();

  //printf("mem: %p len: %ld\n", mem, len);

  aggr[0] = mem + (start << 12);
  for (size_t i = 0x1000; i < len; i += 0x1000, idx++) {
    int dist = idx - prev_index;
    aggr[1] = mem + i;

    uint64_t start = ns();

    for (int j = 0; j < 1000; j++) {
      *(aggr[0]);
      *(aggr[1]);
      isb();
      #ifdef FLUSH
      flush((void*) aggr[0]);
      flush((void*) aggr[1]);
      #endif
    }

    uint64_t duration = ns() - start;

    //printf("%ld\n", duration / 1000);

#ifdef FLUSH
    if (duration / 1000 > 215) {  //56000
#else
    if (duration / 1000 > 125) {  // 23000
#endif
      uintptr_t paddr = get_ppn((uintptr_t) mem + i) * 0x1000;
      distance_history.push_back(dist);
      prev_index = idx;

      if (contiguous) {
        //printf("%d %ld\n", dist, bank_idx);
        //printf(COLOR_GREEN "%2d %p  %6ld %2d " COLOR_RESET, dist, mem + i, 
        //      ((int64_t) paddr - prev_paddr) / 0x1000, get_row_number(paddr));
        //print_addressing_bits(paddr);
        //printf("\n");

        contiguous = false;
        for (int j = 0; j < 4; j++) {
          auto it = distance_history.end();
          std::advance(it, -16);

          if (match_pattern(contiguous_memory_distance_pattern[j], 16, 
                        std::vector<int>(it, distance_history.end()), 16)) {
            contiguous = true;
            break;
          }
        }

        if (contiguous) {
          // we are still in contiguous memory
          if (mem[i] == 0xFF) {
            // we already found this area
            //printf("We already found this area\n");
            //return -1;
          }

          mem[i] = 0xFF;
          rows.push_back((uint8_t*) mem + i);
        }
        else {
          //printf("contiguous STOPPED! length: %ld\n", rows.size());
          if (bank_idx - contiguous_start_idx > 15) {
            return rows.size();
          }
          else {
            rows.clear();
          }
        }
      }
      else if (dist == 8) {
        //printf(COLOR_BLUE "\r%2d %p" COLOR_RESET, dist, mem + i);
        //flush(stdout);

        if (distance_history.size() >= 16) {
          contiguous = false;
          //printf("%d ------------------- %ld / %ld\n", dist, idx, len / 0x1000);

          for (int j = 0; j < 4; j++) {
            auto it = distance_history.end();
            std::advance(it, -16);

            if (match_pattern(contiguous_memory_distance_pattern[j], 16, 
                          std::vector<int>(it, distance_history.end()), 16)) {
              contiguous = true;
              break;
            }
          }
          

          if (contiguous) {
            auto distance = distance_history.end();
            std::advance(distance, -16);
            uintptr_t start_row = (uintptr_t) mem + i - 128 * 0x1000;

            contiguous_start_idx = bank_idx;
            //printf("contiguous %ld %lx\\o/\n", contiguous_start_idx, start_row);

            for (; distance != distance_history.end();) {
              //printf(COLOR_YELLOW "%2d 0x%lx\n" COLOR_RESET, *distance, start_row);
              rows.push_back((uint8_t*) start_row);
              *((uint8_t*) start_row) = 0xFF;
              start_row += *(distance++) * 0x1000;
            }
          }
        }
      }
      else {
        //printf(COLOR_MAGENTA "\r%2d %p" COLOR_RESET, dist, mem + i);
        //flush(stdout);
      }

      prev_paddr = paddr;

      bank_idx++;
    }
//#ifndef FLUSH
//    else if (duration / 1000 < 3500) {
//      //return 0;
//    }
//#endif
    else {
      if (contiguous && dist > 15) {
        //printf("contiguous STOPPED! length: %ld\n", rows.size());
        chunks.push_back(bank_idx - contiguous_start_idx);
        contiguous = false;

        if (bank_idx - contiguous_start_idx > 20) {
          return rows.size();
        }
        else {
          rows.clear();
        }
      }
    }
  }

  if (contiguous) {
    return rows.size();
  }

  return 0;
}


// the offset argument is not used with huge pages
int get_rows(std::vector<uint8_t*> &rows, volatile uint8_t *mem,
             size_t mem_size, int &contig_area_done) {

  int rows_found = 0;

#ifdef USE_HUGEPAGES
  int brc = 0;
  int choosen_paddrs;
  uint64_t offset = -1;

  if(sizeof(search_paddrs) > 0) {
    printf("searching physical addresses\n");
    for (uintptr_t o = 0; o < mem_size && offset == -1; o += 0x200000) {
      uint64_t ppn = get_ppn((intptr_t) (mem + o));
      for (int a = 0; a < sizeof(search_paddrs) / sizeof(uintptr_t); a += 2) {
        if (search_paddrs[a] != 0 && ppn == search_paddrs[a] / 0x1000) {
          offset = o;
          choosen_paddrs = a;
          brc = search_paddrs[a + 1];
          printf("found physical address %lx \\o/ offset = %lx\n", 
                search_paddrs[a], offset);
          break;
        }
      }
    }
  }

  if (offset == -1) {
    printf("did not find physical address\ntaking a random page\n");
    int j;
    for (j = 0; j < 100; j++) {
      int rnd = rand();
      offset = (rnd % (mem_size / 0x200000)) * 0x200000;
      int ppn = get_ppn((uintptr_t) mem + offset);
      if (ppn < 0x70000) {
        break;
      }
      else if (ppn < 0x100000) {
        continue;
      }
      else {
        break;
      }
    }
    if (j == 10000) {
      printf("didn't find page\n");
      return 0;
    }

    brc = rand() % 8;
  }

  rows_found = find_rows_hugepage(mem + offset, 0x200000, rows, brc);

  if (choosen_paddrs != -1) {
    search_paddrs[choosen_paddrs] = 0;
  }
#else
  static int tries = 1;
  static uint64_t offset = 0;

  contig_area_done = 0;

  rows_found = find_rows_no_hugepage(mem + offset, mem_size - offset, rows, 0);

  printf("Found %d contiguous rows\n", rows_found);
  //flush(stdout);

  if (rows_found > 0 || rows_found == -1) {
    if (rows[0] > mem + offset + 64 * 0x1000 && tries != 1) {
      tries = 1;
      offset = (uint64_t) rows[rows_found-1] - (uint64_t) mem;
      contig_area_done = 2;
      return rows_found;
    }


    offset = 0;
    
    if (rows_found > 0) {
      for (int i = 1; i < 16; i++) {
        if (rows[0][i * 0x1000] != 0xFF) {
          offset = (uintptr_t) &(rows[0][i * 0x1000]) - (uintptr_t) mem;
          //printf("Found next offset with i = %d, %p\n", i, mem + offset);
          break;
        }
      }
    }
    else {
      for (int i = 1; i < 16; i++) {
        if (mem[offset + i * 0x1000] != 0xFF) {
          offset = offset + i * 0x1000;
          //printf("Found next offset with i = %d, %p\n", i, mem + offset);
          break;
        }
      }
    }

    if (offset == 0) {
      // we found all banks
      offset = (uint64_t) rows[rows_found-1] - (uint64_t) mem;
      contig_area_done = 1;
      tries = 0;
    }

    if (tries == 16) {
      tries = 0;
      offset = (uint64_t) rows[rows_found-1] - (uint64_t) mem;
      contig_area_done = 1;
    }

    tries++;
  }
#endif

  return rows_found;
}



#ifndef USE_HUGEPAGES
void remove_duplicate_contig_areas(std::vector<ContigMemArea> &contig_mem_areas) {
  printf("remove_duplicate_contig_areas\n");

  for (auto &contig_mem_area : contig_mem_areas) {

    for (int rvi1 = 0; rvi1 < contig_mem_area.rows_vector.size(); rvi1++) {
      auto &rows1 = contig_mem_area.rows_vector[rvi1];

      for (int rvi2 = rvi1 + 1; rvi2 < contig_mem_area.rows_vector.size(); rvi2++) {
        auto &rows2 = contig_mem_area.rows_vector[rvi2];

        bool found_duplicate = false;

        // fast check
        if (rows1.front() > rows2.back() || rows2.front() > rows1.back()) {
          // the memory areas do not overlap -> they cannot be a duplicate
          continue;
        }
      
        // detail check
        for (int ri1 = 0; ri1 < rows1.size() && !found_duplicate; ri1++) {
          for (int ri2 = 0; ri2 < rows2.size(); ri2++) {
            if (rows1[ri1] == rows2[ri2]) {
              found_duplicate = true;
              break;
            }
          }
        }

        if (found_duplicate) {
          if (rows1.size() > rows2.size()) {
            printf("removing mem area (rows2) %d\n", rvi2);
            contig_mem_area.rows_vector.erase(contig_mem_area.rows_vector.begin() + rvi2);
            rvi2--;
          }
          else {
            printf("removing mem area (rows1) %d\n", rvi1);
            contig_mem_area.rows_vector.erase(contig_mem_area.rows_vector.begin() + rvi1);
            rvi1--;
            rvi2--;
            break;
          }
        }
      }
    }
  }

  printf("done\n");
}


void sort_rows(std::vector<ContigMemArea> &contig_mem_areas) {
  int n = 0;

  for (auto &contig_mem_area : contig_mem_areas) {
    uintptr_t base_address = 0;
    uintptr_t base_paddress = 1ULL << 32;    // the memory area shouldn't be bigger than a TB

    for (auto &rows : contig_mem_area.rows_vector) {
      for (int i = 0; i < rows.size() - 1; i++) {
        if (rows[i] == rows[i + 1] - 0x1000) {
          // the physical address bits 16 and 17 of rows[i + 1] are 0
          // we can only guess bit 18 but we say it's always 0. 50/50 chance.
          base_address = (uintptr_t) rows[i + 1];
        }
      }
    }

    if (base_address == 0) {
      //printf("Didn't find bank 0!\n");
      continue;
    }

    // now we have the base address and can calculate the row remapping from 
    // there for any other address in this contiguous area.
    for (auto &rows : contig_mem_area.rows_vector) {
      for (int i = 0; i < rows.size(); i++) {
        int row_number = get_row_number(base_paddress + (uintptr_t) rows[i] - base_address, 0);
        *((int*) rows[i]) = row_number;
      }
    }

    // no we can sort the rows by the row_number

    for (auto &rows : contig_mem_area.rows_vector) {
      std::sort(rows.begin(), rows.end(), sort_rows_predicate());
    }


    /* debug printing
    if (n < 3) {
      int i = 0;
      for (auto &row : contig_mem_area.rows_vector[0]) {
        if (i > 64)
          break;

        printf("%p %d %d %ld\n", row, *((int*) row),
               get_row_number(get_ppn((uintptr_t) row) * 0x1000, 0),
               get_ppn((uintptr_t) row));
        i++;
      }
    
      printf("\n\n");
    }*/

    n++;
  }
}
#endif


// get vectors of physically contiguous rows
int get_rows_vector(std::vector<std::vector<uint8_t*>> &rows_vector,
                    volatile uint8_t *mem, size_t mem_size, int limit) {
  
#ifdef USE_HUGEPAGES

#else
  std::vector<ContigMemArea> contig_mem_areas;
  int found_rows;

  uint64_t start_time = ns();

  do {
    ContigMemArea contig_mem_area;
    std::vector<uint8_t*> rows;
    int contig_area_done;
    
    do {
      found_rows = get_rows(rows, mem, mem_size, contig_area_done);
      
      if (found_rows > 0) {
        if (contig_area_done == 0) {
          contig_mem_area.rows_vector.emplace_back(rows);
          //printf("Found %d rows\n", found_rows);
        }
        else if (contig_area_done == 1) {
          contig_mem_area.rows_vector.emplace_back(rows);
          contig_mem_areas.push_back(contig_mem_area);
          //printf("Found %d rows\n\n", found_rows);
        }
        else if (contig_area_done == 2) {
          contig_mem_areas.push_back(contig_mem_area);
          //printf("\n");

          contig_mem_area.rows_vector.clear();
          contig_mem_area.rows_vector.emplace_back(rows);

          //printf("Found %d rows\n", found_rows);
        }
      }
      else {
        contig_mem_areas.push_back(contig_mem_area);
      }
    } while(!contig_area_done && found_rows > 0);

    limit--;
  } while (found_rows > 0 && (limit > 0 || limit < 0));
  
  uint64_t duration = ns() - start_time;

  remove_duplicate_contig_areas(contig_mem_areas);

  int rows_length = 0;

  for (auto &contig_mem_area : contig_mem_areas) {
    for (auto &rows : contig_mem_area.rows_vector) {
      rows_length += rows.size();
    }
  }

  printf("\rFound %ld contiguous memory areas\n", contig_mem_areas.size());
  printf("Total length: %d rows\n", rows_length);
  printf("Took %ld ms\n", duration / (1000UL * 1000));

  sort_rows(contig_mem_areas);

  //for (auto rows : rows_vector) {
  //  printf("%ld\n", rows.size());
  //}

  for(auto &contig_mem_area : contig_mem_areas) {
    /*for (auto &rows : contig_mem_area.rows_vector) {
      if (rows.size() > 2000) {
        continue;
      }

      rows_vector.push_back(rows);
    }*/

    rows_vector.insert(rows_vector.end(),
                       contig_mem_area.rows_vector.begin(),
                       contig_mem_area.rows_vector.end());
  }
  
  return (int) rows_length;
#endif
}