Line data    Source code

       1             : /*
       2             :  *
       3             :  *    Copyright (c) 2021 Project CHIP Authors
       4             :  *    Copyright 2019 Google Inc. All Rights Reserved.
       5             :  *
       6             :  *    Licensed under the Apache License, Version 2.0 (the "License");
       7             :  *    you may not use this file except in compliance with the License.
       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, software
      13             :  *    distributed under the License is distributed on an "AS IS" BASIS,
      14             :  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      15             :  *    See the License for the specific language governing permissions and
      16             :  *    limitations under the License.
      17             :  */
      18             : 
      19             : #include "PrivateHeap.h"
      20             : 
      21             : #include <string.h>
      22             : 
      23             : #include <lib/support/CodeUtils.h>
      24             : #include <lib/support/logging/CHIPLogging.h>
      25             : 
      26             : namespace {
      27             : 
      28             : constexpr uint32_t kInvalidHeapBlockSize = 0xFFFFFFFF;
      29             : constexpr int32_t kHeapBlockInUse        = 0x01;
      30             : constexpr int32_t kHeapBlockFree         = 0x10;
      31             : constexpr int32_t kInvalidHeaderState    = 0xff;
      32             : 
      33             : using internal::PrivateHeapBlockHeader;
      34             : 
      35             : // this makes life easier, no need to add align offsets.
      36             : static_assert(sizeof(PrivateHeapBlockHeader) % kPrivateHeapAllocationAlignment == 0, "Invalid block size.");
      37             : 
      38        1703 : uint32_t ComputeHeapBlockChecksum(const PrivateHeapBlockHeader * header)
      39             : {
      40        1703 :     uint32_t checksum = header->prevBytes;
      41        1703 :     checksum *= 31;
      42        1703 :     checksum += header->nextBytes;
      43        1703 :     checksum *= 31;
      44        1703 :     checksum += header->state;
      45        1703 :     return checksum;
      46             : }
      47             : 
      48             : // Advances the heap block to the next value
      49         633 : PrivateHeapBlockHeader * NextHeader(PrivateHeapBlockHeader * start)
      50             : {
      51         633 :     if (start->nextBytes == kInvalidHeapBlockSize)
      52             :     {
      53          27 :         return nullptr;
      54             :     }
      55             : 
      56         606 :     if (start->checksum != ComputeHeapBlockChecksum(start))
      57             :     {
      58           0 :         ChipLogError(Support, "Corrupted heap: checksum is invalid");
      59           0 :         chipDie();
      60             :     }
      61             : 
      62         606 :     return reinterpret_cast<PrivateHeapBlockHeader *>(reinterpret_cast<char *>(start) + sizeof(PrivateHeapBlockHeader) +
      63         606 :                                                       start->nextBytes);
      64             : }
      65             : 
      66             : // Advances the heap block to the previous value
      67         103 : PrivateHeapBlockHeader * PreviousHeader(PrivateHeapBlockHeader * start)
      68             : {
      69         103 :     if (start->prevBytes == kInvalidHeapBlockSize)
      70             :     {
      71          47 :         return nullptr;
      72             :     }
      73             : 
      74          56 :     if (start->checksum != ComputeHeapBlockChecksum(start))
      75             :     {
      76           0 :         ChipLogError(Support, "Corrupted heap: checksum is invalid");
      77           0 :         chipDie();
      78             :     }
      79             : 
      80          56 :     return reinterpret_cast<PrivateHeapBlockHeader *>(reinterpret_cast<char *>(start) - sizeof(PrivateHeapBlockHeader) -
      81          56 :                                                       start->prevBytes);
      82             : }
      83             : 
      84         649 : void ValidateHeader(const PrivateHeapBlockHeader * header)
      85             : {
      86         649 :     if (header->state != kHeapBlockFree && header->state != kHeapBlockInUse)
      87             :     {
      88           0 :         ChipLogError(Support, "Invalid header state (neither free nor in use) at %p", header);
      89           0 :         chipDie();
      90             :     }
      91             : 
      92         649 :     if (header->checksum != ComputeHeapBlockChecksum(header))
      93             :     {
      94           0 :         ChipLogError(Support, "Corrupted heap: checksum is invalid at %p", header);
      95           0 :         chipDie();
      96             :     }
      97         649 : }
      98             : 
      99             : } // namespace
     100             : 
     101           9 : extern "C" void PrivateHeapInit(void * heap, size_t size)
     102             : {
     103           9 :     if (heap == nullptr)
     104             :     {
     105           0 :         ChipLogError(Support, "Cannot initialize null heap");
     106           0 :         chipDie();
     107             :     }
     108             : 
     109           9 :     if (size < 2 * sizeof(PrivateHeapBlockHeader))
     110             :     {
     111           0 :         ChipLogError(Support, "Insufficient space in private heap");
     112           0 :         chipDie();
     113             :     }
     114             : 
     115           9 :     if (reinterpret_cast<uintptr_t>(heap) % kPrivateHeapAllocationAlignment != 0)
     116             :     {
     117           0 :         ChipLogError(Support, "Invalid alignment for private heap initialization");
     118           0 :         chipDie();
     119             :     }
     120             : 
     121           9 :     PrivateHeapBlockHeader * header = reinterpret_cast<PrivateHeapBlockHeader *>(heap);
     122             : 
     123           9 :     header->prevBytes = kInvalidHeapBlockSize;
     124           9 :     header->nextBytes = static_cast<uint32_t>(size - 2 * sizeof(PrivateHeapBlockHeader));
     125           9 :     header->state     = kHeapBlockFree;
     126           9 :     header->checksum  = ComputeHeapBlockChecksum(header);
     127             : 
     128           9 :     header            = NextHeader(header);
     129           9 :     header->nextBytes = kInvalidHeapBlockSize;
     130           9 :     header->prevBytes = static_cast<uint32_t>(size - 2 * sizeof(PrivateHeapBlockHeader));
     131           9 :     header->state     = kHeapBlockFree; // does not matter really
     132           9 :     header->checksum  = ComputeHeapBlockChecksum(header);
     133           9 : }
     134             : 
     135         130 : extern "C" void * PrivateHeapAlloc(void * heap, size_t size)
     136             : {
     137         130 :     PrivateHeapBlockHeader * header = reinterpret_cast<PrivateHeapBlockHeader *>(heap);
     138             : 
     139             :     // we allocate aligned, no matter what
     140         130 :     if (size % kPrivateHeapAllocationAlignment != 0)
     141             :     {
     142          40 :         size += kPrivateHeapAllocationAlignment - (size % kPrivateHeapAllocationAlignment);
     143             :     }
     144             : 
     145         567 :     for (; header != nullptr; header = NextHeader(header))
     146             :     {
     147         540 :         ValidateHeader(header);
     148             : 
     149         540 :         if (header->nextBytes == kInvalidHeapBlockSize)
     150             :         {
     151          27 :             continue;
     152             :         }
     153             : 
     154         513 :         if (header->state != kHeapBlockFree)
     155             :         {
     156         403 :             continue; // not free
     157             :         }
     158             : 
     159         110 :         if (header->nextBytes < size)
     160             :         {
     161           7 :             continue; // insufficient space
     162             :         }
     163             : 
     164         103 :         if (header->nextBytes - size < sizeof(PrivateHeapBlockHeader) + kPrivateHeapAllocationAlignment)
     165             :         {
     166             :             // allocate the entire block
     167          61 :             header->state    = kHeapBlockInUse;
     168          61 :             header->checksum = ComputeHeapBlockChecksum(header);
     169             :         }
     170             :         else
     171             :         {
     172             :             // splits the block into two
     173             :             //
     174             :             // +--------+       +--------+       +------+
     175             :             // | header |  ---> | middle |  ---> | next |
     176             :             // +--------+       +--------+       +------+
     177             :             //
     178          42 :             PrivateHeapBlockHeader * next = NextHeader(header);
     179          42 :             PrivateHeapBlockHeader * middle =
     180          42 :                 reinterpret_cast<PrivateHeapBlockHeader *>(reinterpret_cast<char *>(header + 1) + size);
     181             : 
     182             :             // middle is a new block
     183          42 :             middle->nextBytes = static_cast<uint32_t>(header->nextBytes - size - sizeof(PrivateHeapBlockHeader));
     184          42 :             middle->prevBytes = static_cast<uint32_t>(size);
     185          42 :             middle->state     = kHeapBlockFree;
     186          42 :             middle->checksum  = ComputeHeapBlockChecksum(middle);
     187             : 
     188             :             // fix up the header
     189          42 :             header->nextBytes = static_cast<uint32_t>(size);
     190          42 :             header->state     = kHeapBlockInUse;
     191          42 :             header->checksum  = ComputeHeapBlockChecksum(header);
     192             : 
     193             :             // fix up the final block
     194          42 :             if (next != nullptr)
     195             :             {
     196          42 :                 next->prevBytes = middle->nextBytes;
     197          42 :                 next->checksum  = ComputeHeapBlockChecksum(next);
     198             :             }
     199             :         }
     200             : 
     201             :         // we can now use the header
     202         103 :         return header + 1; // data right after the header
     203             :     }
     204             : 
     205             :     // no space found
     206          27 :     return nullptr;
     207             : }
     208             : 
     209         103 : extern "C" void PrivateHeapFree(void * ptr)
     210             : {
     211         103 :     if (ptr == nullptr)
     212             :     {
     213             :         // freeing NULL pointers is always acceptable and a noop
     214           0 :         return;
     215             :     }
     216             : 
     217         103 :     PrivateHeapBlockHeader * header =
     218             :         reinterpret_cast<PrivateHeapBlockHeader *>(static_cast<char *>(ptr) - sizeof(PrivateHeapBlockHeader));
     219             : 
     220         103 :     ValidateHeader(header);
     221         103 :     header->state    = kHeapBlockFree;
     222         103 :     header->checksum = ComputeHeapBlockChecksum(header);
     223             : 
     224             :     // Merge with previous
     225             :     //
     226             :     // +-------+                          +--------+
     227             :     // | other |  ----- nextBytes ----->  | header |
     228             :     // +-------+                          +--------+
     229             :     //
     230         103 :     PrivateHeapBlockHeader * other = PreviousHeader(header);
     231         103 :     if (other != nullptr && other->state == kHeapBlockFree && other->nextBytes != kInvalidHeapBlockSize)
     232             :     {
     233             :         // includes the free bytes in this block in the previous
     234          20 :         other->nextBytes += static_cast<uint32_t>(header->nextBytes + sizeof(PrivateHeapBlockHeader));
     235          20 :         other->checksum = ComputeHeapBlockChecksum(other);
     236          20 :         header->state   = kInvalidHeaderState;
     237          20 :         header          = other;
     238             : 
     239             :         // fixes up the next block
     240          20 :         other = NextHeader(header);
     241          20 :         if (other != nullptr)
     242             :         {
     243          20 :             other->prevBytes = header->nextBytes;
     244          20 :             other->checksum  = ComputeHeapBlockChecksum(other);
     245             :         }
     246             :     }
     247             : 
     248             :     // Merge with next
     249             :     //
     250             :     // +--------+                          +-------+
     251             :     // | header |  ----- nextBytes ----->  | other |
     252             :     // +--------+                          +-------+
     253             :     //
     254         103 :     other = NextHeader(header);
     255         103 :     if (other != nullptr && other->state == kHeapBlockFree && other->nextBytes != kInvalidHeapBlockSize)
     256             :     {
     257             :         // includes the free bytes in the next block
     258          22 :         other->state = kInvalidHeaderState;
     259          22 :         header->nextBytes += static_cast<uint32_t>(other->nextBytes + sizeof(PrivateHeapBlockHeader));
     260          22 :         header->checksum = ComputeHeapBlockChecksum(header);
     261             : 
     262             :         // fixes up the next block
     263          22 :         other = NextHeader(header);
     264          22 :         if (other != nullptr)
     265             :         {
     266          22 :             other->prevBytes = header->nextBytes;
     267          22 :             other->checksum  = ComputeHeapBlockChecksum(other);
     268             :         }
     269             :     }
     270             : }
     271             : 
     272           7 : void * PrivateHeapRealloc(void * heap, void * ptr, size_t size)
     273             : {
     274           7 :     if (ptr == nullptr)
     275             :     {
     276           1 :         return PrivateHeapAlloc(heap, size);
     277             :     }
     278             : 
     279           6 :     if (size == 0)
     280             :     {
     281           0 :         PrivateHeapFree(ptr);
     282           0 :         return nullptr;
     283             :     }
     284             : 
     285           6 :     PrivateHeapBlockHeader * header =
     286             :         reinterpret_cast<PrivateHeapBlockHeader *>(static_cast<char *>(ptr) - sizeof(PrivateHeapBlockHeader));
     287             : 
     288           6 :     ValidateHeader(header);
     289             : 
     290           6 :     if (header->nextBytes >= size)
     291             :     {
     292           3 :         return ptr; // no reallocation needed
     293             :     }
     294             : 
     295           3 :     void * largerCopy = PrivateHeapAlloc(heap, size);
     296           3 :     if (largerCopy == nullptr)
     297             :     {
     298             :         // NOTE: original is left untouched (not freed) to match realloc() libc
     299             :         // functionality
     300           2 :         return nullptr;
     301             :     }
     302             : 
     303           1 :     memcpy(largerCopy, ptr, header->nextBytes);
     304           1 :     PrivateHeapFree(ptr);
     305             : 
     306           1 :     return largerCopy;
     307             : }
     308             : 
     309           0 : extern "C" void PrivateHeapDump(void * top)
     310             : {
     311           0 :     PrivateHeapBlockHeader * header = reinterpret_cast<PrivateHeapBlockHeader *>(top);
     312             : 
     313           0 :     ChipLogProgress(Support, "========= HEAP ===========");
     314           0 :     while (header->nextBytes != kInvalidHeapBlockSize)
     315             :     {
     316           0 :         ChipLogProgress(Support, "    %td: size: %d, state: %d", reinterpret_cast<char *>(header) - reinterpret_cast<char *>(top),
     317             :                         static_cast<int>(header->nextBytes), static_cast<int>(header->state));
     318             : 
     319           0 :         header = NextHeader(header);
     320             :     }
     321           0 : }