Doubts on Virtually Indexed,Physically tagged Cache

I tried referring a few material (videos on youtube and this link as well), but I still couldn’t wrap my head around the concept.

My (brief) understanding of the Virtually addressed, Physically addressed and Virtually indexed Physically tagged cache:

Virtually addressed cache
The virtual address generated by the CPU is used to perform a cache read/write. In the case of a miss the address is translated into a physical address and the appropriate data is loaded into cache and the cache directory is updated. The Translation Look-aside Buffer (TLB) is only used during a cache miss, i.e. when the virtual address is to be converted to a physical address. The cache directory stores a virtual tag.

Physically addressed cache
The physical address acquired from the TLB translation of the virtual address (virtual number + page offset => physical number + page offset) is utilised to perform a cache read/write. The tag stored in the cache directory is the physical tag.

Virtually indexed, Physically tagged cache
The virtual address is forwarded to both TLB and cache. The cache uses the index from the virtual address and finds the corresponding physical tag from the cache directory, the TLB finds the corresponding physical tag from the virtual address and the two tags (from cache directory and TLB) are compared to check if it was a hit/miss.

From what I understood, the cache index and block offset values derived from the logical address could either be equal (with respect to size) to the page offset or not, i.e the page offset either contains the index and block offset or not.
When the size of the index plus block offset do not equal the page offset, wouldn’t the size of the physical tag of the cache directory not match the physical tag of the TLB ? And if that is true, how are the physical tags from the cache directory and TLB compared ? Further more, I also could not understand how Virtually indexed, Physically tagged cache could have the synonym problem when the size of the index plus block offset dont match the page offset.

Doubts in some inequalities used in asymptotic analysis

I was going through this recent paper, and I had a couple of doubts in the final analysis of complexity of the scheme (you don’t need to go through the whole paper). I included three questions here, as I thought they seem to simple questions.

  1. In Pg 17 (last four lines, see after equation 7), there is this inequality that is used (here, $ k(n) = \sqrt{\frac{n\delta(n)}{\log n}}$ and $ \delta(n) = o(n / \log n)$ ):

$ \frac{\binom{n}{a}}{\binom{^n/_k}{^a/_k}^k} \leq (^n/_k)^k$

Can I know a proof for it?

  1. Similarly, in the beginning of Pg 18, how is this possible? (the above inequality is used to get here though, $ (n / k)^{k / 2}$ thing, and don’t worry about the meaning of $ \mathtt{ss}$ )

$ \mathtt{ss} \leq \sqrt{\binom{n}{\frac{n}{2}-\delta(n)}}\cdot (n / k)^{k / 2} \cdot \binom{k}{2\delta(n)} \cdot 2^{(2\delta(n)+1)n / k} \leq 2^{n / 2 + o(n)}$

  1. Also, this one might be a bit trivial, in Pg 17, one inequality above equation 7, the $ O(n)$ term is dropped, isn’t that relevant?

Misra C++ 2008: 5-0-15 doubts about the benefits

I’m writing code for embedded systems (IAR compiler) and it should adhere to Misra C++ 2008. This limits the available features of the language quite a bit (no C++1x features, use of the standard library is banned as well). We use PC-Lint to check for adherence.

Rule 5-0-15 of Misra states:

Array indexing is the only acceptable form of pointer arithmetic, because it is clearer and hence less error prone than pointer manipulation. This rule bans the explicit calculation of pointer values. Array indexing shall only be applied to objects defined as an array type. […]

I have marked the sentence which my question is revolving around. I’ve written a small file system for our external flash memory and the file table itself resides in an EEPROM. The way to access the external EEPROM is a bit awkward. So basically I have to derive the class from CConfigElement and I get handed a byte pointer and a data size and that array of bytes will be synchronized to the EEPROM (just for context).

I have a known maximum number of files, I know the data size is sufficient for the number of file entries I want. My table is basically just an array of file entries. So I cast the byte pointer to a file entry pointer and work on that with array indexing.

That is clearly forbidden by the rule because the table is just a pointer and not an array. Often we are using an exception to the rule and just move on, like it is done in the code below.

class CCeMiniFileSystem : public CConfigElement { public:  bool GetFileInfo(const SoftwareImageSelector_t fileSelector, const uint32_t fileMaxSize, bool& isNewFile,                   uint32_t& baseAddress, uint32_t& currentSize);  void UpdateCurrentSize(const SoftwareImageSelector_t fileSelector, const uint32_t fileMaxSize,                        const uint32_t additionalBytesWritten);  void SetItsData(uint8_t* const d, const uint32_t size) {     CConfigElement::SetItsData(d, size);     fileTable = reinterpret_cast<FileEntry_t*>(data); }  private:  struct FileEntry_t {     SoftwareImageSelector_t selector;     uint32_t baseAddressInFlash;     uint32_t currentSizeInFlash;     uint32_t MaxSize; };  static const uint32_t   MAX_NUMBER_OF_FILES = 7U; FileEntry_t* fileTable; //Pointer to a FileEntry_t-Array with 7 Elements  bool FindFile(const SoftwareImageSelector_t fileSelector, const uint32_t fileMaxSize,                bool& fileExists, uint32_t& fileEntryIndex) const {     fileExists     = false;     fileEntryIndex = 0U;     while ((fileExists == false) && (fileEntryIndex < MAX_NUMBER_OF_FILES))     {         FileEntry_t& entry = fileTable[fileEntryIndex]; //lint !e1960 5-0-15 careful handling of array implemented          if (entry.selector.StorageLocation != 2U)         {             // no more valid entries available (Storage Location must be 2)             // break here --> fileEntryIndex contains index for new file             break;         }         if (true == (entry.selector == fileSelector))         {             if (entry.MaxSize != fileMaxSize)             {                 return false; //lint !e904 file already exists return directly             }             else             {                 fileExists = true;             }         }         else         {             fileEntryIndex++; // only increment if file not found         }     }      return true; }  }; 

But I asked myself: Can I do better – can I write code that complies with the rule?

So I changed the simple pointer to FileEntry_t to a pointer to an array of known number of elements. This required to change the cast when I get the data pointer and it requires that I now dereference the pointer before I can access the element of the array. Like so (I’ve omitted some parts which are the same as before):

class CCeMiniFileSystem : public CConfigElement { public: //... void SetItsData(uint8_t* const d, const uint32_t size) {     CConfigElement::SetItsData(d, size);     fileTable = reinterpret_cast<FileEntry_t(*)[MAX_NUMBER_OF_FILES]>(data); }  private:  struct FileEntry_t { //... };  static const uint32_t   MAX_NUMBER_OF_FILES = 7U; FileEntry_t (* fileTable)[MAX_NUMBER_OF_FILES]; //Pointer to a FileEntry_t-Array with 7 Elements  bool FindFile(const SoftwareImageSelector_t fileSelector, const uint32_t fileMaxSize,                bool& fileExists, uint32_t& fileEntryIndex) const {     fileExists     = false;     fileEntryIndex = 0U;     while ((fileExists == false) && (fileEntryIndex < MAX_NUMBER_OF_FILES))     {         FileEntry_t& entry = (*fileTable)[fileEntryIndex]; //...     return true; }  }; 

So now I’m not really impressed with this.

The doubts I’m having:

  • FileEntry_t (* fileTable)[MAX_NUMBER_OF_FILES]; is not going to be very well understood by everyone around me
  • the necessary dereferenciation makes it not easier to read or understand
  • fileTable[index] is also code which does something, but something entirely different than in the case before

So is code quality (performance is not an issue, it’s readability, maintainability and being less error prone) really improved by adhering to the rule in this case?

Indian evisa doubts

If I have a double entry indian tourist evisa, after I entry twice in India this Visa is cancelled? I mean, do I have to apply for a new Visa? Another question is,Multi entry evisa allows me to entry in India with the same Visa as many times I want for a year? Thanks

Immortality doubts [on hold]

I’m pretty new at DMing, if you guys could give me some hints about this I would appreciate. One of my players is a megalomaniac necromancer who wants to make every living creature immortal, he wants to end death. What kind of information or research about means could I give to him to make his quest more interesting? I thought of something like having to find the research or library of a lich or something, but that sounds to obvious.