Use apt-file para pesquisar o conteúdo dos pacotes.
Para instalar e criar o índice do arquivo:
sudo apt-get install apt-file
sudo apt-file update
Para pesquisar:
apt-file search predefs.h
Isso fornecerá um nome de pacote e um caminho absoluto para onde o arquivo será instalado.
Se isso não retornar nada, pesquise o diretório de pacotes do Ubuntu usando a pesquisa de conteúdo do pacote (verifique se você tem sua versão selecionado no campo "Distribuição".
Se isso não trouxer nada, meu último conselho seria para o Google (por exemplo, o pacote do Ubuntu trusty predefs.h) - embora, devo avisá-lo, o que você encontra pode não ser tão seguro quanto o outros dois métodos.