Expondo NSDictionary

Expor NSDictionary

As tabelas hash são simplesmente fantásticas. Até hoje acho fascinante que seja possível buscar um objeto correspondente a uma chave arbitrária em um tempo constante. Embora o iOS 6.0 tenha introduzido uma tabela hash explícita, é o NSDictionary que é usado quase exclusivamente para armazenamento associativo. Tabelas hash são ótimas. Até hoje ainda acho muito interessante obter o objeto correspondente a qualquer chave em um período fixo de tempo. Embora o iOS 6.0 tenha introduzido tabelas hash explícitas, o NSDictionary é usado quase exclusivamente para armazenamento associativo.

NSDictionary não faz nenhuma promessa de sua implementação interna. Faria pouco sentido para um dicionário armazenar seus dados de forma completamente aleatória. No entanto, esta suposição não responde à questão principal: o NSDictionary faz uso de uma tabela hash? Isso é o que decidi investigar. O NSDictionary não faz promessas sobre sua implementação interna. Não faz sentido um dicionário armazenar dados de forma completamente aleatória. No entanto, esta suposição não responde à questão principal: o NSDictionary usa uma tabela hash? Foi isso que decidi investigar.

Por que não abordar o NSMutableDictionary completo? Um dicionário mutável é, compreensivelmente, muito mais complexo e a quantidade de desmontagem que eu teria que passar era assustadora. O NSDictionary regular ainda oferecia um desafio não trivial de decifração ARM64. Apesar de imutável, a classe possui alguns detalhes de implementação muito interessantes que devem tornar o passeio seguinte agradável. Por que não apenas lidar com um NSMutableDictionary completo? Compreensivelmente, um dicionário mutável é muito mais complexo, e a quantidade de fatoração que eu precisaria fazer seria horrível. O NSDictionary simples ainda apresenta um desafio significativo de decodificação ARM64. Embora esta classe seja imutável, ela possui alguns detalhes de implementação muito interessantes que devem tornar o processo abaixo agradável.

Esta postagem do blog tem um repositório complementar que contém trechos de código discutidos. Embora toda a investigação tenha sido baseada no SDK do iOS 7.1 direcionado a um dispositivo de 64 bits, nem o iOS 7.0 nem os dispositivos de 32 bits impactam as descobertas. Esta postagem do blog tem um repositório contendo os trechos de código discutidos. Embora toda a investigação tenha sido baseada no SDK do iOS 7.1 para dispositivos de 64 bits, nem o iOS 7.0 nem os dispositivos de 32 bits afetaram as descobertas.

A classe Classe

Muitas classes Foundation são clusters de classes e o NSDictionary não é exceção. Por muito tempo o NSDictionary usou o CFDictionary como sua implementação padrão, no entanto, a partir do iOS 6.0 as coisas mudaram: Muitas classes básicas são clusters de classes e o NSDictionary não é exceção. Por algum tempo, o NSDictionary usou o CFDictionary como implementação padrão, no entanto, a partir do iOS 6.0, as coisas mudaram:

(lldb) po [[NSDictionary new] class]
__NSDictionaryI

Da mesma forma que __NSArrayM, __NSDictionaryI está dentro da estrutura CoreFoundation, apesar de ser apresentado publicamente como parte da Foundation. Executar a biblioteca por meio de class-dump gera o seguinte layout ivar: Assim como __NSArrayM, __NSDictionaryI vive dentro da estrutura CoreFoundation, embora seja exposto publicamente como parte da Foundation. Executar a biblioteca por meio de um dump de classe produz o seguinte layout ivar:

@interface __NSDictionaryI : NSDictionary
{
    NSUIngeter _used:58;
    NSUIngeter _szidx:6;
}

É surpreendentemente curto. Não parece haver nenhuma indicação para armazenamento de chaves ou objetos. Como veremos em breve, __NSDictionary literalmente mantém seu armazenamento para si mesmo. É surpreendentemente curto. Não parece haver nenhuma indicação de chaves ou armazenamento de objetos. Como veremos em breve, __NSDictionary literalmente mantém seu armazenamento.

O armazenamento de armazenamento

Criação de instância criação de instância

Para entender onde __NSDictionaryI mantém seu conteúdo, vamos fazer um rápido tour pelo processo de criação da instância. Existe apenas um método de classe responsável por gerar novas instâncias de __NSDictionaryI. De acordo com o class-dump, o método possui a seguinte assinatura: Para entender onde o conteúdo de __NSDictionaryI é salvo, vamos dar uma olhada rápida no processo de criação da instância. Existe apenas um método de classe responsável por gerar novas instâncias de __NSDictionaryI. De acordo com o class-dump, este método possui as seguintes características:

+ (id)__new:(const id *)arg1:(const id *)arg2:(unsigned long long)arg3:(_Bool)arg4:(_Bool)arg5;

São necessários cinco argumentos, dos quais apenas o primeiro é nomeado. Sério, se você fosse usá-lo em uma instrução @selector, ele teria o formato @selector(__new:::::). matriz de objetos e número de chaves (objetos), respectivamente. Observe que as matrizes de chaves e objetos são trocadas em comparação com a API pública, que assume a forma de: São necessários cinco parâmetros, dos quais apenas o primeiro é nomeado. Sério, se você usá-lo em uma instrução @selector, ele terá o formato @selector(__new:::::). Os primeiros três parâmetros podem ser facilmente deduzidos definindo um ponto de interrupção no método e examinando o conteúdo dos registros x2, x3 e x4 contendo a matriz de chaves, a matriz de objetos e a contagem de chaves (objeto), respectivamente. Observe que as chaves e as matrizes de objetos são trocadas em comparação com a API pública, que assume o formato:

+ (instancetype)dictionaryWithObjects:(const id [])objects forKeys:(const id <NSCopying> [])keys count:(NSUInteger)cnt;

Não importa se um argumento é definido como const id * ou const id [], pois os arrays se transformam em ponteiros quando passados como argumentos de função. Não importa se o parâmetro é definido como const id * ou const id[], pois a matriz decairá para um ponteiro quando passada como parâmetro de função.Com três argumentos cobertos, ficamos com os dois parâmetros booleanos não identificados. Fiz algumas pesquisas em assembly e obtive os seguintes resultados: o quarto argumento determina se as chaves devem ser copiadas e o último decide se os argumentos não devem ser retidos. Agora podemos reescrever o método com parâmetros nomeados: Com três parâmetros, ficamos com dois parâmetros booleanos não identificados. Fiz algumas pesquisas na montagem e aqui está o que descobri: o quarto parâmetro controla se a chave deve ser copiada e o último parâmetro determina se o parâmetro não deve ser preservado. Agora podemos substituir este método por parâmetros nomeados:

+ (id)__new:(const id *)keys :(const id *)objects :(unsigned long long)count :(_Bool)copyKeys :(_Bool)dontRetain;

Infelizmente, não temos acesso explícito a este método privado, portanto, ao usar os meios regulares de alocação, os dois últimos argumentos são sempre definidos como YES e NO, respectivamente. No entanto, é interessante que o __NSDictionaryI seja capaz de um controle mais sofisticado de teclas e objetos. Infelizmente, não podemos acessar explicitamente esse método privado, portanto, ao usar o método de alocação regular, os dois últimos parâmetros são sempre definidos como SIM e NÃO, respectivamente. No entanto, é interessante notar que __NSDictionaryI é capaz de fornecer controles de chaves e objetos mais complexos.

####Variáveis de instância indexadas por ivars indexados

Percorrer a desmontagem de + __new::::: revela que malloc e calloc não foram encontrados em lugar nenhum. Em vez disso, o método chama __CFAllocateObject2 passando a classe __NSDictionaryI como primeiro argumento e solicitando o tamanho do armazenamento como segundo. Entrar no mar do ARM64 mostra que a primeira coisa que __CFAllocateObject2 faz é chamar class_createInstance exatamente com os mesmos argumentos. Navegar pela decomposição de + __new:::: revela que nem malloc nem calloc existem. Em vez disso, o método chama __CFAllocateObject2, passando a classe __NSDictionaryI como o primeiro parâmetro e o tamanho de armazenamento solicitado como o segundo parâmetro. Entrar no oceano do ARM64 mostra que a primeira coisa que __CFAllocateObject2 faz é chamar class_createInstance exatamente com os mesmos parâmetros.

Felizmente, neste ponto temos acesso ao código-fonte do tempo de execução do Objective-C, o que torna muito mais fácil uma investigação mais aprofundada. Felizmente, agora temos acesso ao código-fonte do tempo de execução do Objective-C, o que facilita pesquisas futuras.

A função class_createInstance(Class cls, size_t extraBytes) apenas chama _class_createInstanceFromZone ​​passando nil como uma zona, mas esta é a etapa final da alocação de objetos. Embora a função em si tenha muitas verificações adicionais para diferentes circunstâncias, sua essência pode ser abordada com apenas três linhas: A função class_createInstance(Class cls, size_t extraBytes) apenas chama _class_createInstanceFromZone e passa nil como a zona, mas esta é a última etapa da alocação de objetos. Embora a função em si tenha muitas verificações adicionais para diferentes situações, sua essência pode ser descrita em três linhas:

_class_createInstanceFromZone(Class cls, size_t extraBytes, void *zone)
{
    ...
    size_t size = cls->alignedInstanceSize() + extraBytes;
    ...
    id obj = (id)calloc(1, size);
    ...
    return obj;
}

O argumento extraBytes não poderia ter sido mais descritivo. É literalmente o número de bytes extras que aumentam o tamanho da instância padrão. Como um bônus adicional, observe que é a chamada calloc que garante que todos os ivars sejam zerados quando o objeto for alocado. Um argumento de terabyte não poderia ser melhor. Na verdade, são os bytes extras que aumentam o tamanho da instância padrão. Além disso, observe que a chamada calloc garante que todos os ivars sejam zerados quando o objeto for alocado.

A seção de ivars indexados nada mais é do que um espaço adicional que fica no final dos ivars regulares: A parte do índice ivars nada mais é do que um espaço extra no final dos ivars regulares:

Alocando objetos

Alocar espaço por si só não parece muito emocionante, então o tempo de execução publica um acessador: Alocar espaço individualmente não parece interessante, então o tempo de execução publica um acessador:

void *object_getIndexedIvars(id obj)

Não há mágica alguma nesta função, ela apenas retorna um ponteiro para o início da seção ivars indexada: Não há nada de mágico nesta função, ela apenas retorna um ponteiro para o início da seção do índice ivars:

Seção de Ivars indexados

Existem algumas coisas interessantes sobre os ivars indexados. Primeiro de tudo, cada instância pode ter uma quantidade diferente de bytes extras dedicados a ela. Este é exatamente o recurso que o __NSDictionaryI utiliza. Existem algumas coisas interessantes sobre a indexação de ivars. Primeiro, cada instância pode ter uma quantidade diferente de bytes extras. Isso é exatamente o que __NSDictionaryI usa.

Em segundo lugar, proporcionam acesso mais rápido ao armazenamento. Tudo se resume a ser compatível com o cache. De modo geral, saltar para locais de memória aleatórios (desreferenciando um ponteiro) pode ser caro. Como o objeto acabou de ser acessado (alguém chamou um método nele), é muito provável que seus ivars indexados tenham pousado no cache. Ao manter tudo o que é necessário bem próximo, o objeto pode proporcionar o melhor desempenho possível. Em segundo lugar, eles fornecem acesso mais rápido ao armazenamento. Tudo se resume à facilidade de uso do cache. Em geral, saltar para um local de memória aleatório (desreferenciando um ponteiro) pode ser caro. Como o objeto acabou de ser acessado (alguém chamou um método nele), seu índice ivar provavelmente já está no cache. Ao manter tudo o que é necessário muito próximo, os objetos podem proporcionar o melhor desempenho possível.

Finalmente, os ivars indexados podem ser usados ​​como uma medida defensiva grosseira para tornar o interior do objeto invisível para os utilitários, como o despejo de classe. Esta é uma proteção muito básica, pois um invasor dedicado pode simplesmente procurar chamadas object_getIndexedIvars na desmontagem ou sondar aleatoriamente a instância além de sua seção ivars regular para ver o que está acontecendo. Finalmente, os índices ivars podem ser usados ​​como uma medida de defesa grosseira para que utilitários como o class dump não possam ver a estrutura interna de um objeto. Esta é uma proteção muito básica, pois um invasor dedicado poderia simplesmente procurar a chamada object_getIndexedIvars na desmontagem ou sondar aleatoriamente a instância por meio de sua parte ivars regular para ver o que está acontecendo.Embora poderosos, os ivars indexados vêm com duas ressalvas. Primeiro de tudo, class_createInstance não pode ser usado no ARC, então você terá que compilar algumas partes da sua classe com o sinalizador -fno-objc-arc para fazê-la brilhar. Em segundo lugar, o tempo de execução não mantém as informações de tamanho do ivar indexadas em lugar nenhum. Mesmo que dealloc limpe tudo (como chama free internamente), você deve manter o tamanho do armazenamento em algum lugar, supondo que use um número variável de bytes extras. Embora o índice ivar seja poderoso, há dois pontos a serem observados. Primeiro, class_createInstance não funciona no ARC, então você precisa compilar algumas partes da classe com o sinalizador -fno-objc-arc para fazê-la brilhar. Segundo, as informações de tamanho do índice ivar não são salvas em nenhum lugar durante a execução. Mesmo que dealloc limpe tudo (porque chama free internamente), você deve preservar o tamanho do armazenamento, supondo que use uma quantidade variável de bytes extras.

Procurando por chave e buscando objeto Procurando por chaves e recuperando objetos

Analisando Montagem Análise de Montagem

Embora neste ponto pudéssemos cutucar as instâncias __NSDictionaryI para descobrir como elas funcionam, a verdade última está na montagem. Em vez de percorrer toda a parede do ARM64, discutiremos o código Objective-C equivalente. Embora neste ponto possamos dar uma olhada nas instâncias __NSDictionaryI para ver como elas funcionam, a verdade última está na montagem. Discutiremos o código Objective-C equivalente, em vez de todo o ARM64.

A classe em si implementa poucos métodos, mas afirmo que o mais importante é objectForKey: – é isso que discutiremos com mais detalhes. Como de qualquer maneira fiz a análise da montagem, você pode lê-la em uma página separada. É denso, mas a passagem completa deve convencê-lo de que o código a seguir está mais ou menos correto. A classe em si implementa poucos métodos, mas acho que o mais importante é objectForKey: - isso é algo que discutiremos com mais detalhes. Como fiz a análise da compilação, você pode lê-la em uma página separada. É denso, mas a passagem completa levará você a acreditar que o código abaixo está mais ou menos correto.

O código C Código C

Infelizmente, não tenho acesso à base de código da Apple, então o código de engenharia reversa abaixo não é idêntico à implementação original. Por outro lado, parece estar funcionando bem e ainda não encontrei um caso extremo que se comporte de maneira diferente em comparação com o método genuíno. Infelizmente, não tenho acesso à base de código da Apple, portanto o código de engenharia reversa abaixo não é idêntico à implementação original. Por outro lado, parece funcionar muito bem e não encontrei nenhum caso em que se comporte de maneira diferente do método real.

O código a seguir foi escrito da perspectiva da classe __NSDictionaryI : O código a seguir foi escrito da perspectiva da classe __NSDictionaryI:

- (id)objectForKey:(id)aKey
{
    NSUInteger sizeIndex = _szidx;
    NSUInteger size = __NSDictionarySizes[sizeIndex];
    
    id *storage = (id *)object_getIndexedIvars(dict);
    
    NSUInteger fetchIndex = [aKey hash] % size;
    
    for (int i = 0; i < size; i++) {
        id fetchedKey = storage[2 * fetchIndex];

        if (fetchedKey == nil) {
            return nil;
        }
        
        if (fetchedKey == aKey || [fetchedKey isEqual:aKey]) {
            return storage[2 * fetchIndex + 1];
        }

        fetchIndex++;
        
        if (fetchIndex == size) {
            fetchIndex = 0;
        }
    }
    
    return nil;
}

Ao examinar mais de perto o código C, você poderá notar algo estranho na busca de chaves. É sempre obtido de deslocamentos pares, enquanto o objeto retornado está no próximo índice. Esta é a revelação do armazenamento interno do __NSDictionaryI: ele mantém chaves e objetos alternadamente: Ao observar atentamente o código C, você poderá notar algumas peculiaridades na aquisição de chaves. Sempre ocorre um deslocamento par e o objeto retornado está no próximo índice. Esta é uma falha fatal no armazenamento interno do __NSDictionaryI: ele salva chaves e objetos alternadamente:

Chaves e objetos são armazenados alternadamente

Atualização: Joan Lluch forneceu uma explicação muito convincente para este layout. O código original poderia usar uma série de estruturas muito simples: Atualização: Joan Lluch deu uma explicação muito convincente deste layout. O código original pode usar um conjunto muito simples de estruturas:

struct KeyObjectPair {
    id key;
    id object;
};

O método objectForKey: é muito simples e eu recomendo fortemente que você o analise mentalmente. Mesmo assim, vale ressaltar algumas coisas. Em primeiro lugar, o ivar _szidx é usado como um índice no array __NSDictionarySizes, portanto, provavelmente significa “índice de tamanho”. O método objectForKey: é muito simples e eu recomendo fortemente que você o revise mentalmente. Apesar disso, há alguns pontos que merecem destaque. Primeiro, o ivar _szidx é usado como um índice no array __nsdictionarysize, então provavelmente representa o “índice de tamanho”.

Em segundo lugar, o único método chamado na chave passada é hash. O lembrete de dividir o valor hash da chave pelo tamanho do dicionário é usado para calcular o deslocamento na seção de índice ivars. Segundo, o único método chamado na chave passada é o hash. O hash da chave de lembrete dividido pelo tamanho do dicionário é usado para calcular o deslocamento na parte ivars do índice.

Se a chave no deslocamento for nil, simplesmente retornamos nil, o trabalho está concluído: Se a chave for nula no deslocamento, apenas retornaremos nil e o trabalho estará concluído:

Quando o slot da chave está vazio, nil é retornado

No entanto, se a chave no deslocamento não for nil, os dois casos poderão ocorrer. Se as chaves forem iguais, retornamos o objeto adjacente. Se eles não forem iguais, ocorreu a colisão de hash e temos que continuar procurando mais. __NSDictionaryI simplesmente continua procurando até que uma correspondência ou nil seja encontrado: No entanto, ambos os casos são possíveis se a chave no deslocamento não for nula. Se os valores das chaves forem iguais, os objetos adjacentes serão retornados. Se não forem iguais, ocorre uma colisão de hash e temos que continuar procurando. __nsdictionari continua procurando até encontrar uma correspondência ou nada:

Chave encontrada após uma colisãoEsse tipo de pesquisa é conhecido como sondagem linear. Observe como o __NSDictionaryI envolve o fetchIndex quando o fim do armazenamento é atingido. O loop for existe para limitar o número de verificações – se o armazenamento estivesse cheio e a condição do loop estivesse faltando, continuaríamos procurando para sempre. Esta pesquisa é chamada de sondagem linear. Observe como __NSDictionaryI envolve o fetchIndex quando ele atinge o lado do armazenamento. O loop for é usado para limitar o número de verificações - se o armazenamento estiver cheio e a condição do loop estiver faltando, continuaremos procurando.

####__NSDictionarySizes e __NSDictionaryCapacities

Já sabemos que __NSDictionarySizes é algum tipo de array que armazena diferentes tamanhos possíveis de __NSDictionaryI. Podemos raciocinar que é um array de NSUIntegers e, de fato, se pedirmos a Hopper para tratar os valores como inteiros sem sinal de 64 bits, de repente faz muito sentido: Já sabemos que __nsdictionarysize é algum tipo de array que armazena __NSDictionaryI de tamanhos diferentes. Podemos inferir que é um array de NSUIntegers e, de fato, se pedirmos a Hopper para tratar esses valores como inteiros não assinados de 64 bits, de repente faz sentido:

___NSDictionarySizes:
0x00000000001577a8         dq         0x0000000000000000
0x00000000001577b0         dq         0x0000000000000003
0x00000000001577b8         dq         0x0000000000000007
0x00000000001577c0         dq         0x000000000000000d
0x00000000001577c8         dq         0x0000000000000017
0x00000000001577d0         dq         0x0000000000000029
0x00000000001577d8         dq         0x0000000000000047
0x00000000001577e0         dq         0x000000000000007f
...

Numa forma decimal mais familiar, apresenta-se como uma bela lista de 64 primos começando com a seguinte sequência: 0, 3, 7, 13, 23, 41, 71, 127. Observe que estes não são primos consecutivos, o que levanta a questão: qual é a razão média dos dois números vizinhos? Na verdade, é em torno do 1.637 – uma correspondência muito próxima do 1.625, que foi o fator de crescimento do NSMutableArray. Para obter detalhes sobre por que os números primos são usados ​​para o tamanho do armazenamento, esta resposta do Stack Overflow é um bom começo. Numa forma decimal mais familiar, representa uma bela lista de 64 números primos, começando com a seguinte sequência: 0, 3, 7, 13, 23, 41, 71, 127. Observe que estes não são números primos consecutivos. Isso levanta a questão: qual é a proporção média de dois números adjacentes? Na verdade, está em torno de 1,637, o que está muito próximo do fator de crescimento de 1,625 do NSMutableArray. Para obter mais detalhes sobre por que números primos são usados ​​para tamanhos de armazenamento, esta resposta do Stack Overflow é um bom começo.

Já sabemos quanto armazenamento o __NSDictionaryI pode ter, mas como ele sabe qual tamanho de índice escolher na inicialização? A resposta está no método de classe + __new::::: mencionado anteriormente. A conversão de algumas partes da montagem de volta para C renderiza o seguinte código: Já sabemos quanto armazenamento __NSDictionaryI pode ter, mas como saber qual tamanho de índice escolher no momento da inicialização? A resposta está no método de classe + __new:::: mencionado anteriormente. A conversão de algumas partes da montagem de volta para C renderiza o seguinte código:

int szidx;
for (szidx = 0; szidx < 64; szidx++) {
    if (__NSDictionaryCapacities[szidx] >= count) {
        break;
    }
}

if (szidx == 64) {
    goto fail;
}

O método examina linearmente o array __NSDictionaryCapacities até que a contagem se ajuste ao tamanho. Uma rápida olhada no Hopper mostra o conteúdo do array: Este método pesquisa linearmente na matriz __nsdictionarycapacity até que a contagem corresponda a esse tamanho. Numa rápida olhada no Hopper, o conteúdo do array é o seguinte:

___NSDictionaryCapacities:
0x00000000001579b0         dq         0x0000000000000000
0x00000000001579b8         dq         0x0000000000000003
0x00000000001579c0         dq         0x0000000000000006
0x00000000001579c8         dq         0x000000000000000b
0x00000000001579d0         dq         0x0000000000000013
0x00000000001579d8         dq         0x0000000000000020
0x00000000001579e0         dq         0x0000000000000034
0x00000000001579e8         dq         0x0000000000000055
...

A conversão para base 10 fornece 0, 3, 6, 11, 19, 32, 52, 85 e assim por diante. Observe que esses são números menores que os primos listados anteriormente. Se você encaixasse 32 pares de valores-chave em __NSDictionaryI, ele alocaria espaço para 41 pares, economizando de forma conservadora alguns slots vazios. Isso ajuda a reduzir o número de colisões de hash, mantendo o tempo de busca o mais próximo possível da constante. Tirando o caso trivial de 3 elementos, o __NSDictionaryI nunca terá seu armazenamento cheio, ocupando em média no máximo 62% de seu espaço. A conversão para base 10 fornece 0, 3, 6, 11, 19, 32, 52, 85 e assim por diante. Observe que esses números são menores que os números primos listados anteriormente. Se você colocar 32 pares de valores-chave em __NSDictionaryI, ele alocará espaço para 41 pares de valores-chave, economizando de forma conservadora muitos slots vazios. Isso ajuda a reduzir o número de colisões de hash e mantém o tempo de busca o mais próximo possível da constante. Exceto no caso simples de 3 elementos, o armazenamento do __NSDictionaryI nunca fica cheio, ocupando em média até 62% do espaço.

Como curiosidade, o último valor não vazio de __NSDictionaryCapacities é 0x11089481C742, que é 18728548943682 na base 10. Você teria que se esforçar muito para não se enquadrar no limite de contagem de pares, pelo menos na arquitetura de 64 bits. Como curiosidade, o último valor não nulo de __nsdictionarycapacity é 0x11089481C742, que na base 10 é 18728548943682. Pelo menos em arquiteturas de 64 bits, você tem que se esforçar muito para não cumprir o limite de contagem.

Símbolos não exportados Sinalizador de não exportação

Se você usasse __NSDictionarySizes em seu código, declarando-o como um array extern, perceberia rapidamente que não é tão fácil. O código não foi compilado devido a um erro do vinculador – o símbolo __NSDictionarySizes é indefinido. Inspecionando a biblioteca CoreFoundation com o utilitário nm: Se você usar __nsdictionarysize em seu código declarando __nsdictionarysize como um array externo, você perceberá rapidamente que isso não é fácil. O código não é compilado devido a um erro do vinculador - o símbolo __nsdictionarysize é indefinido. Use a ferramenta nm para verificar a biblioteca CoreFoundation:

nm CoreFoundation | grep ___NSDictionarySizes

…mostra claramente que os símbolos estão lá (para ARMv7, ARMv7s e ARM64 respectivamente): …mostra claramente a presença de símbolos (ARMv7, ARMv7s e ARM64 respectivamente):

00139c80 s ___NSDictionarySizes
0013ac80 s ___NSDictionarySizes
0000000000156f38 s ___NSDictionarySizes

Infelizmente, o manual nm afirma claramente: Infelizmente, o manual nm afirma claramente:

Se o símbolo for local (não externo), o tipo do símbolo é representado pela letra minúscula correspondente.Os símbolos para __NSDictionarySizes simplesmente não são exportados – eles são destinados ao uso interno da biblioteca. Fiz algumas pesquisas para descobrir se é possível vincular símbolos não exportados, mas aparentemente não é (diga-me se for!). Não podemos acessá-los. Ou seja, não podemos acessá-los facilmente. Os símbolos para __nsdictionarysize não são exportados - são para uso interno da biblioteca. Fiz algumas pesquisas e me perguntei se era possível vincular símbolos não exportados, mas aparentemente não é possível (diga-me se é possível!) e não podemos acessá-los. Ou seja, não podemos acessá-los facilmente.

####Esgueirando-se secretamente em

Aqui está uma observação interessante: tanto no iOS 7.0 quanto no 7.1, a constante kCFAbsoluteTimeIntervalSince1904 é apresentada diretamente antes de __NSDictionarySizes: Uma observação interessante aqui: no iOS 7.0 e 7.1, a constante kCFAbsoluteTimeIntervalSince1904 é listada diretamente antes de __nsdictionarysize:

_kCFAbsoluteTimeIntervalSince1904:
0x00000000001577a0         dq         0x41e6ceaf20000000
___NSDictionarySizes:
0x00000000001577a8         dq         0x0000000000000000

O melhor do kCFAbsoluteTimeIntervalSince1904 é que ele é exportado! Vamos adicionar 8 bytes (tamanho de double) ao endereço desta constante e reinterpretar o resultado como um ponteiro para NSUInteger: A melhor coisa sobre o kcfabsolutetimeintervalvalis desde 1904 é que ele é exportado! Adicionaremos 8 bytes (o dobro do tamanho) ao endereço desta constante e reinterpretaremos o resultado como um ponteiro para um NSUInteger:

NSUInteger *Explored__NSDictionarySizes = (NSUInteger *)((char *)&kCFAbsoluteTimeIntervalSince1904 + 8);

Então podemos acessar seus valores por meio de indexação conveniente: Podemos então acessar seu valor através de um índice conveniente:

(lldb) p Explored__NSDictionarySizes[0]
(NSUInteger) $0 = 0
(lldb) p Explored__NSDictionarySizes[1]
(NSUInteger) $1 = 3
(lldb) p Explored__NSDictionarySizes[2]
(NSUInteger) $2 = 7

Este hack é muito frágil e provavelmente irá quebrar no futuro, mas este é o projeto de teste, então está perfeitamente bem. Este hack é muito frágil e provavelmente irá quebrar no futuro, mas este é um projeto de teste, então é perfeito.

__NSDictionaryI Características __NSDictionaryI Características

Agora que descobrimos a estrutura interna do __NSDictionaryI, podemos usar essas informações para descobrir por que as coisas funcionam da maneira que funcionam e quais consequências imprevistas a implementação atual do __NSDictionaryI apresenta. Agora que descobrimos a estrutura interna de __NSDictionaryI, podemos usar essas informações para descobrir por que as coisas funcionam da maneira que funcionam e quais consequências imprevistas a implementação atual de __NSDictionaryI tem.

Código de impressão Código de impressão

Para tornar nossa investigação um pouco mais fácil, criaremos um método de categoria auxiliar NSDictionary que imprimirá o conteúdo da instância Para facilitar nossa pesquisa, criaremos um método auxiliar de categoria NSDictionary que imprimirá o conteúdo da instância

- (NSString *)explored_description
{
    assert([NSStringFromClass([self class]) isEqualToString:@"__NSDictionaryI"]);
    
    BCExploredDictionary *dict = (BCExploredDictionary *)self;

    NSUInteger count = dict->_used;
    NSUInteger sizeIndex = dict->_szidx;
    NSUInteger size = Explored__NSDictionarySizes[sizeIndex];
    
    __unsafe_unretained id *storage = (__unsafe_unretained id *)object_getIndexedIvars(dict);
    
    NSMutableString *description = [NSMutableString stringWithString:@"\n"];
    
    [description appendFormat:@"Count: %lu\n", (unsigned long)count];
    [description appendFormat:@"Size index: %lu\n", (unsigned long)sizeIndex];
    [description appendFormat:@"Size: %lu\n", (unsigned long)size];

    for (int i = 0; i < size; i++) {
        [description appendFormat:@"[%d] %@ - %@\n", i, [storage[2*i] description], [storage[2*i + 1] description]];
    }
    
    return description;
}

A ordem das chaves/objetos na enumeração é igual à ordem das chaves/objetos no armazenamento

A ordem das chaves/objetos no enum é a mesma que a ordem das chaves/objetos no armazenamento

Vamos criar um dicionário simples contendo quatro valores: Vamos criar um dicionário simples com quatro valores:

NSDictionary *dict = @{@1 : @"Value 1",
                       @2 : @"Value 2",
                       @3 : @"Value 3",
                       @4 : @"Value 4"};

NSLog(@"%@", [dict explored_description]);

A saída da descrição explorada é: A saída da descrição explorada é:

Count: 4
Size index: 2
Size: 7
[0] (null) - (null)
[1] 3 - Value 3
[2] (null) - (null)
[3] 2 - Value 2
[4] (null) - (null)
[5] 1 - Value 1
[6] 4 - Value 4

Com isso em mente, vamos fazer uma enumeração rápida no dicionário: Com isso em mente, vamos fazer um rápido dicionário de enumeração:

[dict enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
    NSLog(@"%@ - %@", key, obj);
}];

E a saída: e saída:

3 - Value 3
2 - Value 2
1 - Value 1
4 - Value 4

A enumeração parece simplesmente percorrer o armazenamento, ignorando as chaves nil e chamando o bloco apenas para slots não vazios. Este também é o caso da enumeração rápida, métodos keyEnumerator, allKeys e allValues. Faz todo o sentido. O NSDictionary não está ordenado, então realmente não importa em que sequência as chaves e valores são fornecidos. Usar o layout interno é a opção mais fácil e provavelmente a mais rápida. O enum parece apenas iterar sobre o armazenamento, ignorando chaves nulas e chamando apenas blocos para slots não nulos. Este também é o caso da enumeração rápida, enumeradores de chave, métodos allKeys e allValues. Isso faz todo o sentido. O NSDictionary não é ordenado, portanto a ordem das chaves e valores não importa. Usar um layout interno é a opção mais fácil e rápida.

Se você errar, __NSDictionaryI pode retornar algo com chave nula! Se você errar, __nsdictionaryI posso retornar algo com chave nula!

Vamos considerar um exemplo. Imagine que estamos construindo um jogo de estratégia 3D simples ambientado no espaço. O universo inteiro está dividido em setores semelhantes a cubos pelos quais facções imaginárias podem lutar. Um setor pode ser referenciado pelos seus índices i, j e k. desperdiçaria memória armazenando ponteiros nil. Em vez disso, usaremos um armazenamento esparso na forma de NSDictionary com uma classe de chave personalizada que tornará muito fácil consultar se há algo em um determinado local. Vamos considerar um exemplo. Digamos que estamos construindo um jogo simples de estratégia em 3D. Todo o universo está dividido em áreas cúbicas pelas quais facções imaginárias podem lutar. Um setor pode ser referenciado pelos seus índices i, j e k. Não deveríamos usar um array 3D para armazenar informações do setor - o espaço do jogo é enorme e quase vazio, então estaríamos desperdiçando memória armazenando ponteiros nulos. Em vez disso, usaremos um armazenamento esparso na forma de um NSDictionary, com uma classe de chave personalizada que tornará muito fácil consultar se há algo em um determinado local.

Aqui está a interface da chave, uma classe BC3DIndex: Esta é a interface da chave, uma classe BC3DIndex:

@interface BC3DIndex : NSObject <NSCopying>

@property (nonatomic, readonly) NSUInteger i, j, k; // you actually can do that

- (instancetype)initWithI:(NSUInteger)i j:(NSUInteger)j k:(NSUInteger)k;

@end

E sua implementação igualmente trivial: E sua implementação igualmente trivial:

@implementation BC3DIndex

- (instancetype)initWithI:(NSUInteger)i j:(NSUInteger)j k:(NSUInteger)k
{
    self = [super init];
    if (self) {
        _i = i;
        _j = j;
        _k = k;
    }
    return self;
}

- (BOOL)isEqual:(BC3DIndex *)other
{
    return other.i == _i && other.j == _j && other.k == _k;
}

- (NSUInteger)hash
{
    return _i ^ _j ^ _k;
}

- (id)copyWithZone:(NSZone *)zone
{
    return self; // we're immutable so it's OK
}

@end
```Observe como estamos sendo bons cidadãos de subclasses: implementamos os métodos `isEqual`: e `hash` e garantimos que, se dois índices 3D forem iguais, seus valores de hash também serão iguais. Os requisitos de igualdade de objetos são atendidos.
Observe como estamos sendo bons cidadãos de subclasses: implementamos os métodos isEqual: e hash e nos certificamos de que se dois índices 3d forem iguais, então seus hashes também serão iguais. O requisito de igualdade de objetos é atendido.

Aqui vai uma curiosidade: o que o código a seguir imprimirá?
Aqui está uma pequena pergunta: o que o código a seguir imprimirá?

NSDictionary *indexes = @{[[BC3DIndex alloc] initWithI:2 j:8 k:5] : @“A black hole!”, [[BC3DIndex alloc] initWithI:0 j:0 k:0] : @“Asteroids!”, [[BC3DIndex alloc] initWithI:4 j:3 k:4] : @“A planet!”};

NSLog(@“%@”, [indexes objectForKey:nil]);

Deveria ser `(null)` certo? Não:
Deveria ser (nulo), certo? Não:

Asteroids!

Para investigar isso mais detalhadamente, vamos pegar a descrição de um dicionário:
Para investigar isso mais detalhadamente, vamos obter uma descrição do dicionário:

Count: 3 Size index: 1 Size: 3 [0] <BC3DIndex: 0x17803d340> - A black hole! [1] <BC3DIndex: 0x17803d360> - Asteroids! [2] <BC3DIndex: 0x17803d380> - A planet!

Acontece que `__NSDictionaryI` não verifica se o `key` passado para `objectForKey:` é `nil` (e eu diria que esta é uma boa decisão de design). Chamar o método `hash` em `nil` retorna `0`, o que faz com que a classe compare a chave no índice `0` com `nil`. Isto é importante: é a chave armazenada que executa o método `isEqual:`, não a chave passada.
O resultado é que __nsdictionari não verifica se a chave passada para objectForKey: é nula (o que considero uma boa decisão de design). Chamar o método hash em nil retornará 0, o que fará com que a classe compare a chave no índice 0 com nil. Isso é importante: é a chave armazenada que executa o método isEqual:, não a chave passada.

A primeira comparação falha, pois o índice `i` para “Um buraco negro!” é `2` enquanto para `nil` é zero. As teclas não são iguais o que faz com que o dicionário continue procurando, acertando outra tecla armazenada: a de “Asteróides!”. Esta chave tem todas as três propriedades `i`, `j` e `k` iguais a `0`, que também é o que `nil` retornará quando solicitado por suas propriedades (por meio da verificação `nil` dentro de `objc_msgSend`).
A primeira comparação falhou porque indexei “Um buraco negro!” que é 2 e nil é 0. As duas teclas não são iguais, o que faz com que o dicionário continue procurando e pressione outra tecla armazenada: "Asteróide!" Essa chave possui todos os três atributos i, j e k iguais a 0, que também é o valor que nil retorna ao solicitar seus atributos (por meio da verificação nil em objc_msgSend).

Este é o cerne do problema. A implementação `isEqual:` de `BC3DIndex` pode, sob algumas condições, retornar `YES` para comparação com `nil`. Como você pode ver, esse é um comportamento muito perigoso que pode bagunçar as coisas facilmente. Certifique-se sempre de que seu objeto não seja igual a `nil`.
Este é o cerne da questão. isEqual: Sob certas condições, as implementações de BC3DIndex podem retornar SIM para comparações nulas. Como você pode ver, esse é um comportamento muito perigoso e pode facilmente atrapalhar as coisas. Sempre certifique-se de que o objeto não seja igual a nulo.

#### Uma classe de chave auxiliar Classe de chave auxiliar

Para os próximos dois testes, criaremos uma classe de chave especial que terá um valor de hash configurável e imprimirá coisas no console ao executar os métodos `hash` e `isEqual:`.
Nos próximos dois testes, criaremos uma classe de chave especial que terá um valor de hash configurável e imprimirá o conteúdo no console quando os métodos hash e isEqual: forem executados.

Aqui está a interface:
Esta é a interface:

@interface BCNastyKey : NSObject <NSCopying>

@property (nonatomic, readonly) NSUInteger hashValue;

• (instancetype)keyWithHashValue:(NSUInteger)hashValue;

@end

E a implementação:

@implementation BCNastyKey

• (instancetype)keyWithHashValue:(NSUInteger)hashValue { return [[BCNastyKey alloc] initWithHashValue:hashValue]; }

• (instancetype)initWithHashValue:(NSUInteger)hashValue { self = [super init]; if (self) { _hashValue = hashValue; } return self; }

• (id)copyWithZone:(NSZone *)zone { return self; }

• (NSUInteger)hash { NSLog(@“Key %@ is asked for its hash”, [self description]);

  return _hashValue; }

• (BOOL)isEqual:(BCNastyKey *)object { NSLog(@“Key %@ equality test with %@: %@”, [self description], [object description], object == self ? @“YES” : @“NO”);

  return object == self; }

• (NSString *)description { return [NSString stringWithFormat:@“(&:%p #:%lu)”, self, (unsigned long)_hashValue]; }

@end

Essa chave é horrível: somos iguais apenas a nós mesmos, mas estamos retornando um hash arbitrário. Observe que isso não quebra o contrato de igualdade.
Essa chave é ruim: nós apenas igualamos a nós mesmos, mas retornamos um hash arbitrário. Observe que isso não viola o contrato de igualdade.

#### isEqual não precisa ser chamado para corresponder à chave

Vamos criar uma chave e um dicionário:
Vamos criar uma chave e um dicionário:

BCNastyKey *key = [BCNastyKey keyWithHashValue:3]; NSDictionary *dict = @{key : @“Hello there!”};

A seguinte chamada:
Os seguintes números de telefone:

[dict objectForKey:key];

Imprime isso no console:
Imprimir no console:

Key (&:0x17800e240 #:3) is asked for its hash

Como você pode ver, o método `isEqual:` não foi chamado. Isso é muito legal! Como a grande maioria das chaves existentes são literais `NSString`, elas compartilham o mesmo endereço em todo o aplicativo. Mesmo que a chave seja uma string literal muito longa, o `__NSDictionaryI` não executará o método `isEqual:` potencialmente demorado, a menos que seja absolutamente necessário. E como as arquiteturas de 64 bits introduziram ponteiros marcados, algumas instâncias de `NSNumber`, `NSDate` e, aparentemente, `NSIndexPath` também se beneficiam dessa otimização.
Como você pode ver, o método isEqual: ainda não foi chamado. Isso é legal! Como a grande maioria das chaves são literais NSString, elas compartilham o mesmo endereço em todo o aplicativo. Mesmo que a chave seja uma string literal longa, __NSDictionaryI não executará o método isEqual: potencialmente demorado, a menos que seja absolutamente necessário. Como as arquiteturas de 64 bits introduziram ponteiros marcados, algumas instâncias de NSNumber, NSDate e NSIndexPath aparentemente também se beneficiaram dessa otimização.

#### O desempenho do pior caso é linear O desempenho do pior caso é linear

Vamos criar um caso de teste muito simples:
Vamos criar um caso de teste bem simples:

BCNastyKey *targetKey = [BCNastyKey keyWithHashValue:36];

NSDictionary *b = @{[BCNastyKey keyWithHashValue:1] : @1, [BCNastyKey keyWithHashValue:8] : @2, [BCNastyKey keyWithHashValue:15] : @3, [BCNastyKey keyWithHashValue:22] : @4, [BCNastyKey keyWithHashValue:29] : @5, targetKey : @6 };

Uma única linha assassina:
Um trunfo simples:

NSLog(@“Result: %@”, [[b objectForKey:targetKey] description]);

Revela o desastre:
Desastre revelado:

Key (&:0x170017640 #:36) is asked for its hash Key (&:0x170017670 #:1) equality test with (&:0x170017640 #:36): NO Key (&:0x170017660 #:8) equality test with (&:0x170017640 #:36): NO Key (&:0x170017680 #:15) equality test with (&:0x170017640 #:36): NO Key (&:0x1700176e0 #:22) equality test with (&:0x170017640 #:36): NO Key (&:0x170017760 #:29) equality test with (&:0x170017640 #:36): NO Result: 6

Este é um caso extremamente patológico – cada chave do dicionário foi testada em termos de igualdade. Embora cada hash fosse diferente, ele ainda colidia com todas as outras chaves, porque os hashes das chaves eram congruentes no módulo 7, que acabou sendo o tamanho de armazenamento do dicionário.
Este é um caso extremamente patológico - cada chave do dicionário é testada quanto à igualdade de Ben. Mesmo que cada hash seja diferente, ele ainda colide com outras chaves porque o hash da chave é o módulo 7, que é o tamanho de armazenamento do dicionário.Conforme mencionado anteriormente, observe que falta o último teste `isEqual:`. O `__NSDictionaryI` simplesmente comparou os ponteiros e descobriu que devia ser a mesma chave.
Como mencionado antes, observe que o último teste isEqual: está faltando. __nsdictionari simplesmente compara os ponteiros e descobre que eles devem ser da mesma chave.

Você deveria se preocupar com essa busca de tempo linear? Absolutamente não. Não gosto muito de análise probabilística de distribuição de hash, mas você teria que ter muita sorte para que todos os seus hashes fossem módulo congruentes com o tamanho do dicionário. Algumas colisões aqui e ali sempre acontecerão, essa é a natureza das tabelas hash, mas provavelmente você nunca se deparará com o problema do tempo linear. Isto é, a menos que você bagunce sua função `hash`.
Você deveria se preocupar com essa aquisição de tempo linear? Absolutamente não. Não sou um grande fã de análise probabilística de distribuições de hash, mas você precisa ter muita sorte, pois todos os seus hashes têm o módulo do tamanho do dicionário. Sempre haverá algumas colisões aqui e ali, essa é a natureza das tabelas hash, mas provavelmente você nunca encontrará um problema de tempo linear. A menos que você tenha estragado a função hash.

### Palavras FinaisPalavras Finais

Estou fascinado com o quão simples o `__NSDictionaryI` acabou sendo. Escusado será dizer que a classe certamente cumpre o seu propósito e não há necessidade de tornar as coisas excessivamente complexas. Para mim, o aspecto mais bonito da implementação é o layout objeto-chave-objeto-chave. Esta é uma ideia brilhante.
Fiquei intrigado com o quão simples esse dicionário acabou sendo. Escusado será dizer que esta aula certamente cumpre o seu propósito e não há necessidade de complicar as coisas. Para mim, o aspecto mais bonito desta implementação é o layout objeto-chave-objeto-chave. Esta é uma boa ideia.

Se você seguisse uma dica deste artigo, eu ficaria atento aos métodos `hash` e `isEqual:`. É verdade que raramente se escrevem classes de chave personalizadas para serem usadas em um dicionário, mas essas regras também se aplicam ao `NSSet`.
Se você seguir uma dica deste artigo, recomendo prestar atenção aos métodos hash e isEqual:. É verdade que poucas pessoas escrevem classes de chaves personalizadas para uso em dicionários, mas essas regras também se aplicam a NSSets.

Estou ciente de que em algum momento o `NSDictionary` mudará e minhas descobertas se tornarão obsoletas. A internalização dos actuais detalhes de implementação pode tornar-se um fardo no futuro, quando os pressupostos memorizados deixarem de ser aplicáveis. No entanto, aqui e agora é muito divertido ver como as coisas funcionam e espero que você compartilhe do meu entusiasmo.
Eu sei que em algum momento o NSDictionary mudará e minhas descobertas se tornarão obsoletas. A internalização dos detalhes da implementação actual pode tornar-se um fardo futuro quando os pressupostos lembrados já não se aplicarem. No entanto, aqui e agora, é muito divertido ver como as coisas funcionam e espero que você possa compartilhar meu entusiasmo.



Texto original: https://ciechanow.ski/exposing-nsdictionary/