Just An Application

September 27, 2014

Building The Android Runtime (ART) For Mac OS X: Part Four — MemMap::MapAnonymous

File: $(ANDROID_SRC)/art/runtime/mem_map.cc

Method: MemMap::MapAnonymous

    ...
    
    MemMap* MemMap::MapAnonymous(const char* name, byte* expected_ptr, size_t byte_count, int prot,
      bool low_4gb, std::string* error_msg) {
      if (byte_count == 0) {
        return new MemMap(name, nullptr, 0, nullptr, 0, prot, false);
      }
      size_t page_aligned_byte_count = RoundUp(byte_count, kPageSize);
    
      int flags = MAP_PRIVATE | MAP_ANONYMOUS;
      ScopedFd fd(-1);
    
    #ifdef USE_ASHMEM
    #ifdef HAVE_ANDROID_OS
      const bool use_ashmem = true;
    #else
      // When not on Android ashmem is faked using files in /tmp. Ensure that such files won't
      // fail due to ulimit restrictions. If they will then use a regular mmap.
      struct rlimit rlimit_fsize;
      CHECK_EQ(getrlimit(RLIMIT_FSIZE, &rlimit_fsize), 0);
      const bool use_ashmem = (rlimit_fsize.rlim_cur == RLIM_INFINITY) ||
         (page_aligned_byte_count < rlimit_fsize.rlim_cur);
    #endif
      if (use_ashmem) {
        // android_os_Debug.cpp read_mapinfo assumes all ashmem regions associated with the VM are
        // prefixed "dalvik-".
        std::string debug_friendly_name("dalvik-");
        debug_friendly_name += name;
        fd.reset(ashmem_create_region(debug_friendly_name.c_str(), page_aligned_byte_count));
        if (fd.get() == -1) {
          *error_msg = StringPrintf("ashmem_create_region failed for '%s': %s", name, strerror(errno));
          return nullptr;
        }
        flags = MAP_PRIVATE;
      }
    #endif
    
      // We need to store and potentially set an error number for pretty printing of errors
      int saved_errno = 0;
    
    #ifdef __LP64__
      // When requesting low_4g memory and having an expectation, the requested range should fit into
      // 4GB.
      if (low_4gb && (
          // Start out of bounds.
          (reinterpret_cast<uintptr_t>(expected_ptr) >> 32) != 0 ||
          // End out of bounds. For simplicity, this will fail for the last page of memory.
          (reinterpret_cast<uintptr_t>(expected_ptr + page_aligned_byte_count) >> 32) != 0)) {
        *error_msg = StringPrintf("The requested address space (%p, %p) cannot fit in low_4gb",
        expected_ptr, expected_ptr + page_aligned_byte_count);
        return nullptr;
      }
    #endif
    
      // TODO:
      // A page allocator would be a useful abstraction here, as
      // 1) It is doubtful that MAP_32BIT on x86_64 is doing the right job for us
      // 2) The linear scheme, even with simple saving of the last known position, is very crude
    #if USE_ART_LOW_4G_ALLOCATOR
      // MAP_32BIT only available on x86_64.
      void* actual = MAP_FAILED;
      if (low_4gb && expected_ptr == nullptr) {
        bool first_run = true;
    
        for (uintptr_t ptr = next_mem_pos_; ptr < 4 * GB; ptr += kPageSize) {
          if (4U * GB - ptr < page_aligned_byte_count) {
            // Not enough memory until 4GB.
            if (first_run) {
              // Try another time from the bottom;
              ptr = LOW_MEM_START - kPageSize;
              first_run = false;
              continue;
            } else {
              // Second try failed.
              break;
            }
          }
    
          uintptr_t tail_ptr;
    
          // Check pages are free.
          bool safe = true;
          for (tail_ptr = ptr; tail_ptr < ptr + page_aligned_byte_count; tail_ptr += kPageSize) {
            if (msync(reinterpret_cast<void*>(tail_ptr), kPageSize, 0) == 0) {
              safe = false;
              break;
            } else {
              DCHECK_EQ(errno, ENOMEM);
            }
          }
    
          next_mem_pos_ = tail_ptr;  // update early, as we break out when we found and mapped a region
    
          if (safe == true) {
            actual = mmap(reinterpret_cast<void*>(ptr), page_aligned_byte_count, prot, flags, fd.get(),
                          0);
            if (actual != MAP_FAILED) {
              // Since we didn't use MAP_FIXED the kernel may have mapped it somewhere not in the low
              // 4GB. If this is the case, unmap and retry.
              if (reinterpret_cast<uintptr_t>(actual) + page_aligned_byte_count < 4 * GB) {
                break;
              } else {
                munmap(actual, page_aligned_byte_count);
                actual = MAP_FAILED;
              }
            }
          } else {
            // Skip over last page.
            ptr = tail_ptr;
          }
        }
    
        if (actual == MAP_FAILED) {
          LOG(ERROR) << "Could not find contiguous low-memory space.";
          saved_errno = ENOMEM;
        }
      } else {
        actual = mmap(expected_ptr, page_aligned_byte_count, prot, flags, fd.get(), 0);
        saved_errno = errno;
      }
    
    #else
    #if defined(__LP64__)
      if (low_4gb && expected_ptr == nullptr) {
        flags |= MAP_32BIT;
      }
    #endif
    
      void* actual = mmap(expected_ptr, page_aligned_byte_count, prot, flags, fd.get(), 0);
      saved_errno = errno;
    #endif
    
      if (actual == MAP_FAILED) {
        std::string maps;
        ReadFileToString("/proc/self/maps", &maps);
    
        *error_msg = StringPrintf("Failed anonymous mmap(%p, %zd, 0x%x, 0x%x, %d, 0): %s\n%s",
                                  expected_ptr, page_aligned_byte_count, prot, flags, fd.get(),
                                  strerror(saved_errno), maps.c_str());
        return nullptr;
      }
      std::ostringstream check_map_request_error_msg;
      if (!CheckMapRequest(expected_ptr, actual, page_aligned_byte_count, error_msg)) {
        return nullptr;
      }
      return new MemMap(name, reinterpret_cast<byte*>(actual), byte_count, actual,
                        page_aligned_byte_count, prot, false);
    }
    
    ...

Although it is not entirely obvious, amongst the welter of #ifdefs and assorted detritus, there is a for loop hiding in the method.

It is only compiled in if

    USE_ART_LOW_4G_ALLOCATOR

is defined and not 0.

The definition, or otherwise, of USE_ART_LOW_4G_ALLOCATOR occurs in the file

    art/runtime/mem_map.h

and is itself conditional

    ...
    
    #if defined(__LP64__) && (!defined(__x86_64__) || defined(__APPLE__))
    #define USE_ART_LOW_4G_ALLOCATOR 1
    #else
    #define USE_ART_LOW_4G_ALLOCATOR 0
    #endif
    
    ...

so on a 64-bit Mac it will be defined as 1, so the loop is present,

The for loop is inside the if statement

      ...
    
      if (low_4gb && expected_ptr == nullptr) {
      
        ...
        
      }
    
      ...

where

    low_4gb

and

    expected_ptr

are both arguments to the method.

Looking at the caller in this case

File: $(ANDROID_SRC)/art/runtimegc/heap.cc

Method: Heap::MapAnonymousPreferredAddress

    ...
    
    MemMap* Heap::MapAnonymousPreferredAddress(const char* name, byte* request_begin, size_t capacity,
                                               int prot_flags, std::string* out_error_str) {
      while (true) {
        MemMap* map = MemMap::MapAnonymous(kMemMapSpaceName[0], request_begin, capacity,
                                           PROT_READ | PROT_WRITE, true, out_error_str);
        if (map != nullptr || request_begin == nullptr) {
          return map;
        }
        // Retry a  second time with no specified request begin.
        request_begin = nullptr;
      }
      return nullptr;
    }
    
    ...

we can see that the

    low_4gb

argument is always true, and the

    expected_ptr

argument is the value of the method’s

    request_begin

argument, or

    nullptr

so one way or another the MemMap::MapAnonymous method can definitely end up in the loop.

What the method is trying to do in the loop is get the OS to allocate a continuous area of memory of a given size somewhere in the low 4GB of the process address space, starting at the 64K mark and working its way upwards a ‘page’ at a time.

The worst case outcome is that the necessary memory is not available. In this case the loop will iterate over the entire address space, so although it will terminate it will not do so for a very long time.

Here is a simplified version of the loop in the form of a standalone program.


    static constexpr int kPageSize = 4096;

    static constexpr size_t KB = 1024;
    static constexpr size_t GB = KB * KB * KB;

    static constexpr uintptr_t LOW_MEM_START = 64 * KB;

    int main(int argc, const char * argv[])
    {
        void*     actual = MAP_FAILED;
        size_t    nBytes = 16 * kPageSize;

        for (uintptr_t ptr = LOW_MEM_START; ptr < 4 * GB; ptr += kPageSize)
        {
            uintptr_t tail_ptr;
    
            // Check pages are free.
            bool safe = true;
    
            for (tail_ptr = ptr; tail_ptr < ptr + nBytes; tail_ptr += kPageSize)
            {
                if (msync(reinterpret_cast<void*>(tail_ptr), kPageSize, 0) == 0)
                {
                    safe = false;
                    break;
                }
                else
                if (errno == ENOMEM)
                {
                    // not in use
                }
                else
                {
                    // some other error
                    return 1;
                }
            }
            if (safe == true)
            {
                actual = mmap(reinterpret_cast<void*>(ptr), nBytes, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0);
                if (actual != MAP_FAILED)
                {
                    fprintf(stdout, "actual == %p\n", actual);
                    // Since we didn't use MAP_FIXED the kernel may have mapped it somewhere not in the low
                    // 4GB. If this is the case, unmap and retry.
                    if (reinterpret_cast<uintptr_t>(actual) + nBytes < 4 * GB)
                    {
                        break;
                    }
                    else
                    {
                        munmap(actual, nBytes);
                        actual = MAP_FAILED;
                    }
                }
            }
            else
            {
                // Skip over last page.
                ptr = tail_ptr;
            }
        }
        return 0;
    }

and here’s what it prints when it is run

    actual == 0x10cbf5000
    actual == 0x10cbf5000
    actual == 0x10cbf5000
    actual == 0x10cbf5000
    actual == 0x10cbf5000
    actual == 0x10cbf5000
    actual == 0x10cbf5000
    actual == 0x10cbf5000
    
    ... 

effectively forever, or certainly for a lot longer than I am prepared to wait for it to iterate approximately 4G/4K times then terminate.


Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: